Fundamentals of Linear Algebra #

1 - Introduction #

Linear algebra is one of the foundational branches of mathematics, with applications spanning from engineering and computer science to economics and physics. This document is extracted from the textbook Matrix Differential Calculus with Applications in Statistics and Econometrics from Jan R. Magnus; Heinz Neudecker, adapting the notations to the ones used in the lectures.

In this chapter, we summarize some of the well-known definitions and theorems of matrix algebra. Most of the theorems will be proved.

2 - Sets #

Sometimes a set can be defined by displaying the elements in braces. For example, $A={0,1}$ or

$$ \mathbb{N}={1,2,3, \ldots} $$

Notice that $A$ is a finite set (contains a finite number of elements), whereas $\mathbb{N}$ is an infinite set. If $P$ is a property that any element of $S$ has or does not have, then

$$ {x: x \in S, x \text { satisfies } P} $$

denotes the set of all the elements of $S$ that have property $P$.

If $A$ and $B$ are two subsets of $S$, we define

$$ A \cup B, $$

the union of $A$ and $B$, as the set of elements of $S$ that belong to $A$ or to $B$ or to both, and

$$ A \cap B, $$

the intersection of $A$ and $B$, as the set of elements of $S$ that belong to both $A$ and $B$. We say that $A$ and $B$ are (mutually) disjoint if they have no common elements, that is, if

$$ A \cap B=\emptyset . $$

The complement of $A$ relative to $B$, denoted by $B-A$, is the set ${x: x \in B$, but $x \notin A}$. The complement of $A$ (relative to $S$) is sometimes denoted by $A^{c}$.

The set of (finite) real numbers (the one-dimensional Euclidean space) is denoted by $\mathbb{R}$. The $n$-dimensional Euclidean space $\mathbb{R}^{n}$ is the Cartesian product of $n$ sets equal to $\mathbb{R}$:

$$ \mathbb{R}^{n}=\mathbb{R} \times \mathbb{R} \times \cdots \times \mathbb{R} \quad (n \text { times }) $$

The elements of $\mathbb{R}^{n}$ are thus the ordered $n$-tuples $\left(x_{1}, x_{2}, \ldots, x_{n}\right)$ of real numbers $x_{1}, x_{2}, \ldots, x_{n}$.

3 - Matrices: Addition and Multiplication #

If one or more of the elements of $\mathbf{A}$ is complex, we say that $\mathbf{A}$ is a complex matrix. Almost all matrices in this book are real and the word ‘matrix’ is assumed to be a real matrix, unless explicitly stated otherwise.

An $m \times n$ matrix can be regarded as a point in $\mathbb{R}^{m \times n}$. The real numbers $a_{i j}$ are called the elements of $\mathbf{A}$. An $m \times 1$ matrix is a point in $\mathbb{R}^{m \times 1}$ (that is, in $\mathbb{R}^{m}$) and is called a (column) vector of order $m \times 1$. A $1 \times n$ matrix is called a row vector (of order $1 \times n$). The elements of a vector are usually called its components. Matrices are always denoted by capital letters and vectors by lower-case letters.

The following properties are now easily proved for matrices $\mathbf{A}, \mathbf{B}$, and $\mathbf{C}$ of the same order and scalars $\lambda$ and $\mu$:

\begin{equation} \begin{aligned} \mathbf{A}+\mathbf{B} & =\mathbf{B}+\mathbf{A}, \\ (\mathbf{A}+\mathbf{B})+\mathbf{C} & =\mathbf{A}+(\mathbf{B}+\mathbf{C}), \\ (\lambda+\mu) \mathbf{A} & =\lambda \mathbf{A}+\mu \mathbf{A}, \\ \lambda(\mathbf{A}+\mathbf{B}) & =\lambda \mathbf{A}+\lambda \mathbf{B}, \\ \lambda(\mu \mathbf{A}) & =(\lambda \mu) \mathbf{A} . \end{aligned} \end{equation}

A matrix whose elements are all zero is called a null matrix and denoted by $\mathbf{0}$. We have, of course,

$$ \mathbf{A}+(-1) \mathbf{A}=\mathbf{0} $$

The following properties of the matrix product can be established:

\begin{equation} \begin{aligned} (\mathbf{A} \mathbf{B}) \mathbf{C} & =\mathbf{A}(\mathbf{B} \mathbf{C}) \\ \mathbf{A}(\mathbf{B}+\mathbf{C}) & =\mathbf{A} \mathbf{B}+\mathbf{A} \mathbf{C} \\ (\mathbf{A}+\mathbf{B}) \mathbf{C} & =\mathbf{A} \mathbf{C}+\mathbf{B} \mathbf{C} \end{aligned} \end{equation}

These relations hold provided the matrix products exist.

We note that the existence of $\mathbf{A} \mathbf{B}$ does not imply the existence of $\mathbf{B} \mathbf{A}$, and even when both products exist, they are not generally equal. (Two matrices $\mathbf{A}$ and $\mathbf{B}$ for which

$$ \mathbf{A} \mathbf{B}=\mathbf{B} \mathbf{A} $$

are said to commute.) We therefore distinguish between premultiplication and postmultiplication: a given $m \times n$ matrix $\mathbf{A}$ can be premultiplied by a $p \times m$ matrix $\mathbf{B}$ to form the product $\mathbf{B} \mathbf{A}$; it can also be postmultiplied by an $n \times q$ matrix $\mathbf{C}$ to form $\mathbf{A} \mathbf{C}$.

4 - The transpose of a matrix #

We have

\begin{equation} \begin{aligned} \left(\mathbf{A}^{\mathrm{T}}\right)^{\mathrm{T}} & =\mathbf{A} \\ (\mathbf{A}+\mathbf{B})^{\mathrm{T}} & =\mathbf{A}^{\mathrm{T}}+\mathbf{B}^{\mathrm{T}} \\ (\mathbf{A} \mathbf{B})^{\mathrm{T}} & =\mathbf{B}^{\mathrm{T}} \mathbf{A}^{\mathrm{T}} \end{aligned} \end{equation}

If $\mathbf{x}$ is an $n \times 1$ vector, then $\mathbf{x}^{\mathrm{T}}$ is a $1 \times n$ row vector and

$$ \mathbf{x}^{\mathrm{T}} \mathbf{x}=\sum_{i=1}^{n} x_{i}^{2} $$

5 - Square matrices #

A square matrix $\mathbf{A}=\left(a_{i j}\right)$, real or complex, is said to be

A square matrix $\mathbf{A}$ is triangular if it is either lower triangular or upper triangular (or both).

A real square matrix $\mathbf{A}=\left(a_{i j}\right)$ is said to be

For any square $n \times n$ matrix $\mathbf{A}=\left(a_{i j}\right)$, we define $\operatorname{dg} \mathbf{A}$ or $\operatorname{dg}(\mathbf{A})$ as

$$ \operatorname{dg} \mathbf{A}=\left(\begin{array}{cccc} a_{11} & 0 & \ldots & 0 \\ 0 & a_{22} & \ldots & 0 \\ \vdots & \vdots & & \vdots \\ 0 & 0 & \ldots & a_{n n} \end{array}\right) $$

or, alternatively,

$$ \operatorname{dg} \mathbf{A}=\operatorname{diag}\left(a_{11}, a_{22}, \ldots, a_{n n}\right) $$

We sometimes write $\mathbf{I}$ instead of $\mathbf{I}_{n}$ when the order is obvious or irrelevant. We have

$$ \mathbf{I} \mathbf{A}=\mathbf{A} \mathbf{I}=\mathbf{A}, $$

if $\mathbf{A}$ and $\mathbf{I}$ have the same order.

A rectangular (not square) matrix can still have the property that $\mathbf{A} \mathbf{A}^{\mathrm{T}}=\mathbf{I}$ or $\mathbf{A}^{\mathrm{T}} \mathbf{A}=\mathbf{I}$, but not both. Such a matrix is called semi-orthogonal.

Note carefully that the concepts of symmetry, skew-symmetry, and orthogonality are defined only for real square matrices. Hence, a complex matrix $\mathbf{Z}$ satisfying $\mathbf{Z}^{\mathrm{T}}=\mathbf{Z}$ is not called symmetric (in spite of what some textbooks do). This is important because complex matrices can be Hermitian, skew-Hermitian, or unitary, and there are many important results about these classes of matrices. These results should specialize to matrices that are symmetric, skew-symmetric, or orthogonal in the special case that the matrices are real. Thus, a symmetric matrix is just a real Hermitian matrix, a skew-symmetric matrix is a real skew-Hermitian matrix, and an orthogonal matrix is a real unitary matrix; see also Section 1.12.

6 - Linear forms and quadratic forms #

Let $\mathbf{a}$ be an $n \times 1$ vector, $\mathbf{A}$ an $n \times n$ matrix, and $\mathbf{B}$ an $n \times m$ matrix. The expression $\mathbf{a}^{\mathrm{T}} \mathbf{x}$ is called a linear form in $\mathbf{x}$, the expression $\mathbf{x}^{\mathrm{T}} \mathbf{A} \mathbf{x}$ is a quadratic form in $\mathbf{x}$, and the expression $\mathbf{x}^{\mathrm{T}} \mathbf{B} \mathbf{y}$ a bilinear form in $\mathbf{x}$ and $\mathbf{y}$. In quadratic forms we may, without loss of generality, assume that $\mathbf{A}$ is symmetric, because if not then we can replace $\mathbf{A}$ by $\left(\mathbf{A}+\mathbf{A}^{\mathrm{T}}\right) / 2$, since

$$ \mathbf{x}^{\mathrm{T}} \mathbf{A} \mathbf{x}=\mathbf{x}^{\mathrm{T}}\left(\frac{\mathbf{A}+\mathbf{A}^{\mathrm{T}}}{2}\right) \mathbf{x} . $$

Thus, let $\mathbf{A}$ be a symmetric matrix. We say that $\mathbf{A}$ is

It is clear that the matrices $\mathbf{B} \mathbf{B}^{\mathrm{T}}$ and $\mathbf{B}^{\mathrm{T}} \mathbf{B}$ are positive semidefinite, and that $\mathbf{A}$ is negative (semi)definite if and only if $-\mathbf{A}$ is positive (semi)definite. A square null matrix is both positive and negative semidefinite.

The following two theorems are often useful.

7 - The rank of a matrix #

It is clear that

$$ r(\mathbf{A}) \leq \min (m, n) $$

If $r(\mathbf{A})=m$, we say that $\mathbf{A}$ has full row rank. If $r(\mathbf{A})=n$, we say that $\mathbf{A}$ has full column rank. If $r(\mathbf{A})=0$, then $\mathbf{A}$ is the null matrix, and conversely, if $\mathbf{A}$ is the null matrix, then $r(\mathbf{A})=0$.

We have the following important results concerning ranks:

\begin{equation} \begin{gathered} r(\mathbf{A})=r\left(\mathbf{A}^{\mathrm{T}}\right)=r\left(\mathbf{A}^{\mathrm{T}} \mathbf{A}\right)=r\left(\mathbf{A} \mathbf{A}^{\mathrm{T}}\right) \\ r(\mathbf{A} \mathbf{B}) \leq \min (r(\mathbf{A}), r(\mathbf{B})) \\ r(\mathbf{A} \mathbf{B})=r(\mathbf{A}) \quad \text { if } \mathbf{B} \text { is square and of full rank, } \\ r(\mathbf{A}+\mathbf{B}) \leq r(\mathbf{A})+r(\mathbf{B}) \end{gathered} \end{equation}

and finally, if $\mathbf{A}$ is an $m \times n$ matrix and $\mathbf{A} \mathbf{x}=\mathbf{0}$ for some $\mathbf{x} \neq \mathbf{0}$, then

$$ r(\mathbf{A}) \leq n-1 $$

The dimension of this vector space is $r(\mathbf{A})$. We have

$ \mathcal{M}(\mathbf{A})=\mathcal{M}\left(\mathbf{A} \mathbf{A}^{\mathrm{T}}\right) $

for any matrix $\mathbf{A}$.

Exercises:

1. If $\mathbf{A}$ has full column rank and $\mathbf{C}$ has full row rank, then $r(\mathbf{A} \mathbf{B} \mathbf{C})=r(\mathbf{B})$.
2. Let $\mathbf{A}$ be partitioned as $\mathbf{A}=\left(\mathbf{A}_{1}: \mathbf{A}_{2}\right)$. Then $r(\mathbf{A})=r\left(\mathbf{A}_{1}\right)$ if and only if $\mathcal{M}\left(\mathbf{A}_{2}\right) \subset \mathcal{M}\left(\mathbf{A}_{1}\right)$.

8 - The Inverse #

We have

\begin{equation} \begin{aligned} \left(\mathbf{A}^{-1}\right)^{\mathrm{T}} & =\left(\mathbf{A}^{\mathrm{T}}\right)^{-1}, \\ (\mathbf{A} \mathbf{B})^{-1} & =\mathbf{B}^{-1} \mathbf{A}^{-1}, \end{aligned} \end{equation}

if the inverses exist.

It can be proved that any permutation matrix is nonsingular. In fact, it is even true that $\mathbf{P}$ is orthogonal, that is,

$ \mathbf{P}^{-1}=\mathbf{P}^{\mathrm{T}} $

for any permutation matrix $\mathbf{P}$.

9 - The Determinant #

We have

\begin{equation} \begin{aligned} |\mathbf{A} \mathbf{B}| & =|\mathbf{A}||\mathbf{B}| \\ \left|\mathbf{A}^{\mathrm{T}}\right| & =|\mathbf{A}| \\ |\alpha \mathbf{A}| & =\alpha^{n}|\mathbf{A}| \quad \text { for any scalar } \alpha \\ \left|\mathbf{A}^{-1}\right| & =|\mathbf{A}|^{-1} \quad \text { if } \mathbf{A} \text { is nonsingular, } \\ \left|\mathbf{I}_{n}\right| & =1 \end{aligned} \end{equation}

The matrix $\mathbf{C}=\left(c_{i j}\right)$ is called the cofactor matrix of $\mathbf{A}$. The transpose of $\mathbf{C}$ is called the adjoint of $\mathbf{A}$ and will be denoted by $\mathbf{A}^{\#}$.

We have

\begin{equation} \begin{aligned} |\mathbf{A}|=\sum_{j=1}^{n} a_{i j} c_{i j} & =\sum_{j=1}^{n} a_{j k} c_{j k} \quad(i, k=1, \ldots, n), \\ \mathbf{A} \mathbf{A}^{\#} & =\mathbf{A}^{\#} \mathbf{A}=|\mathbf{A}| \mathbf{I}, \\ (\mathbf{A} \mathbf{B})^{\#} & =\mathbf{B}^{\#} \mathbf{A}^{\#} . \end{aligned} \end{equation}

Exercises:

1. If $\mathbf{A}$ is nonsingular, show that $\mathbf{A}^{\#}=|\mathbf{A}| \mathbf{A}^{-1}$.
2. Prove that the determinant of a triangular matrix is the product of its diagonal elements.

10 - The trace #

We have

\begin{equation} \begin{aligned} \operatorname{tr}(\mathbf{A}+\mathbf{B}) & =\operatorname{tr} \mathbf{A}+\operatorname{tr} \mathbf{B} \\ \operatorname{tr}(\lambda \mathbf{A}) & =\lambda \operatorname{tr} \mathbf{A} \quad \text { if } \lambda \text { is a scalar } \\ \operatorname{tr} \mathbf{A}^{\mathrm{T}} & =\operatorname{tr} \mathbf{A} \\ \operatorname{tr} \mathbf{A} \mathbf{B} & =\operatorname{tr} \mathbf{B} \mathbf{A} \end{aligned} \end{equation}

We note in (25) that $\mathbf{A} \mathbf{B}$ and $\mathbf{B} \mathbf{A}$, though both square, need not be of the same order.

Corresponding to the vector (Euclidean) norm

$ |\mathbf{x}|=\left(\mathbf{x}^{\mathrm{T}} \mathbf{x}\right)^{1 / 2}, $

given in (4), we now define the matrix (Euclidean) norm as

We have

$ \operatorname{tr} \mathbf{A}^{\mathrm{T}} \mathbf{A} \geq 0 $

with equality if and only if $\mathbf{A}=\mathbf{0}$.

11 - Partitioned matrices #

Let $\mathbf{B}(m \times n)$ be similarly partitioned into submatrices $\mathbf{B}_{ij}(i, j=1,2)$. Then,

$$ \mathbf{A}+\mathbf{B}=\left(\begin{array}{cc} \mathbf{A}_{11}+\mathbf{B}_{11} & \mathbf{A}_{12}+\mathbf{B}_{12} \\ \mathbf{A}_{21}+\mathbf{B}_{21} & \mathbf{A}_{22}+\mathbf{B}_{22} \end{array}\right) $$

Now let $\mathbf{C}(n \times p)$ be partitioned into submatrices $\mathbf{C}_{ij}(i, j=1,2)$ such that $\mathbf{C}_{11}$ has $n_1$ rows (and hence $\mathbf{C}_{12}$ also has $n_1$ rows and $\mathbf{C}_{21}$ and $\mathbf{C}_{22}$ have $n_2$ rows). Then we may postmultiply $\mathbf{A}$ by $\mathbf{C}$ yielding

$$ \mathbf{A} \mathbf{C}=\left(\begin{array}{cc} \mathbf{A}_{11} \mathbf{C}_{11}+\mathbf{A}_{12} \mathbf{C}_{21} & \mathbf{A}_{11} \mathbf{C}_{12}+\mathbf{A}_{12} \mathbf{C}_{22} \\ \mathbf{A}_{21} \mathbf{C}_{11}+\mathbf{A}_{22} \mathbf{C}_{21} & \mathbf{A}_{21} \mathbf{C}_{12}+\mathbf{A}_{22} \mathbf{C}_{22} \end{array}\right) $$

The transpose of the matrix $\mathbf{A}$ given in (28) is

$$ \mathbf{A}^{\mathrm{T}}=\left(\begin{array}{cc} \mathbf{A}_{11}^{\mathrm{T}} & \mathbf{A}_{21}^{\mathrm{T}} \\ \mathbf{A}_{12}^{\mathrm{T}} & \mathbf{A}_{22}^{\mathrm{T}} \end{array}\right) $$

If the off-diagonal blocks $\mathbf{A}_{12}$ and $\mathbf{A}_{21}$ are both zero, and $\mathbf{A}_{11}$ and $\mathbf{A}_{22}$ are square and nonsingular, then $\mathbf{A}$ is also nonsingular and its inverse is

$$ \mathbf{A}^{-1}=\left(\begin{array}{cc} \mathbf{A}_{11}^{-1} & \mathbf{0} \\ \mathbf{0} & \mathbf{A}_{22}^{-1} \end{array}\right) $$

More generally, if $\mathbf{A}$ as given in (28) is nonsingular and $\mathbf{D}=\mathbf{A}_{22}-\mathbf{A}_{21} \mathbf{A}_{11}^{-1} \mathbf{A}_{12}$ is also nonsingular, then

$$ \mathbf{A}^{-1}=\left(\begin{array}{cc} \mathbf{A}_{11}^{-1}+\mathbf{A}_{11}^{-1} \mathbf{A}_{12} \mathbf{D}^{-1} \mathbf{A}_{21} \mathbf{A}_{11}^{-1} & -\mathbf{A}_{11}^{-1} \mathbf{A}_{12} \mathbf{D}^{-1} \\ -\mathbf{D}^{-1} \mathbf{A}_{21} \mathbf{A}_{11}^{-1} & \mathbf{D}^{-1} \end{array}\right) $$

Alternatively, if $\mathbf{A}$ is nonsingular and $\mathbf{E}=\mathbf{A}_{11}-\mathbf{A}_{12} \mathbf{A}_{22}^{-1} \mathbf{A}_{21}$ is also nonsingular, then

$$ \mathbf{A}^{-1}=\left(\begin{array}{cc} \mathbf{E}^{-1} & -\mathbf{E}^{-1} \mathbf{A}_{12} \mathbf{A}_{22}^{-1} \\ -\mathbf{A}_{22}^{-1} \mathbf{A}_{21} \mathbf{E}^{-1} & \mathbf{A}_{22}^{-1}+\mathbf{A}_{22}^{-1} \mathbf{A}_{21} \mathbf{E}^{-1} \mathbf{A}_{12} \mathbf{A}_{22}^{-1} \end{array}\right) . $$

Of course, if both $\mathbf{D}$ and $\mathbf{E}$ are nonsingular, blocks in (29) and (30) can be interchanged. The results (29) and (30) can be easily extended to a $3 \times 3$ matrix partition. We only consider the following symmetric case where two of the off-diagonal blocks are null matrices.

As to the determinants of partitioned matrices, we note that

$$ \left|\begin{array}{ll} \mathbf{A}_{11} & \mathbf{A}_{12} \\ \mathbf{0} & \mathbf{A}_{22} \end{array}\right|=\left|\mathbf{A}_{11}\right|\left|\mathbf{A}_{22}\right|=\left|\begin{array}{ll} \mathbf{A}_{11} & \mathbf{0} \\ \mathbf{A}_{21} & \mathbf{A}_{22} \end{array}\right| $$

if both $\mathbf{A}_{11}$ and $\mathbf{A}_{22}$ are square matrices.

Exercises:

1. Find the determinant and inverse (if it exists) of

$$ \mathbf{B}=\left(\begin{array}{cc} \mathbf{A} & \mathbf{0} \\ \mathbf{a}^{\mathrm{T}} & 1 \end{array}\right) . $$

2. If $|\mathbf{A}| \neq 0$, prove that

$$ \left|\begin{array}{cc} \mathbf{A} & \mathbf{b} \\ \mathbf{a}^{\mathrm{T}} & \alpha \end{array}\right|=\left(\alpha-\mathbf{a}^{\mathrm{T}} \mathbf{A}^{-1} \mathbf{b}\right)|\mathbf{A}| . $$

3. If $\alpha \neq 0$, prove that

$$ \left|\begin{array}{cc} \mathbf{A} & \mathbf{b} \\ \mathbf{a}^{\mathrm{T}} & \alpha \end{array}\right|=\alpha\left|\mathbf{A}-(1 / \alpha) \mathbf{b} \mathbf{a}^{\mathrm{T}}\right| . $$

12 - Complex Matrices #

If $\mathbf{A}$ and $\mathbf{B}$ are real matrices of the same order, then a complex matrix $\mathbf{Z}$ can be defined as

$$ \mathbf{Z}=\mathbf{A}+i \mathbf{B} $$

where $i$ denotes the imaginary unit with the property $i^2=-1$. The complex conjugate of $\mathbf{Z}$, denoted by $\mathbf{Z}^mathrm{H}$, is defined as

$$ \mathbf{Z}^\mathrm{H}=\mathbf{A}^{\mathrm{T}}-i \mathbf{B}^{\mathrm{T}} $$

If $\mathbf{Z}$ is real, then $\mathbf{Z}^\mathrm{H}=\mathbf{Z}^{\mathrm{T}}$. If $\mathbf{Z}$ is a scalar, say $\zeta$, we usually write $\bar{\zeta}$ instead of $\zeta^mathrm{H}$.

A square complex matrix $\mathbf{Z}$ is said to be Hermitian if $\mathbf{Z}^{\mathrm{H}}=\mathbf{Z}$ (the complex equivalent to a symmetric matrix), skew-Hermitian if $\mathbf{Z}^{\mathrm{H}}=-\mathbf{Z}$ (the complex equivalent to a skew-symmetric matrix), and unitary if $\mathbf{Z}^{\mathrm{H}} \mathbf{Z}=\mathbf{I}$ (the complex equivalent to an orthogonal matrix).

We shall see in this theorem that the eigenvalues of a symmetric matrix are real. In general, however, eigenvalues (and hence eigenvectors) are complex. In this book, complex numbers appear only in connection with eigenvalues and eigenvectors of matrices that are not symmetric (Chapter 8). A detailed treatment is therefore omitted. Matrices and vectors are assumed to be real, unless it is explicitly specified that they are complex.

13 - Eigenvalues and Eigenvectors #

Eigenvectors are usually normalized in some way to make them unique, for example, by $\mathbf{x}^{\mathrm{T}} \mathbf{x}=\mathbf{y}^{\mathrm{T}} \mathbf{y}=1$ (when $\mathbf{x}$ and $\mathbf{y}$ are real).

Not all roots of the characteristic equation need to be different. Each root is counted a number of times equal to its multiplicity. When a root (eigenvalue) appears more than once it is called a multiple eigenvalue; if it appears only once it is called a simple eigenvalue.

Although eigenvalues are in general complex, the eigenvalues of a symmetric matrix are always real.

Let us prove the following three results, which will be useful to us later.

An important theorem regarding positive definite matrices is stated below.

Next, let us prove this theorem.

Without proof we state the following famous result.

Finally, we present the following result on eigenvectors.

Exercices

1. Show that

\begin{equation} \left|\begin{array}{ll} 0 & I_{m} \\ I_{m} & 0 \end{array}\right|=(-1)^{m} \end{equation}

2. Show that, for $n=2$,

\begin{equation} |I+\epsilon \mathbf{A}|=1+\epsilon \operatorname{tr} \mathbf{A}+\epsilon^{2}|\mathbf{A}| \end{equation}

3. Show that, for $n=3$,

\begin{equation} |I+\epsilon \mathbf{A}|=1+\epsilon \operatorname{tr} \mathbf{A}+\frac{\epsilon^{2}}{2}\left((\operatorname{tr} \mathbf{A})^{2}-\operatorname{tr} \mathbf{A}^{2}\right)+\epsilon^{3}|\mathbf{A}| \end{equation}

14 - Schur’s decomposition theorem #

In the next few sections, we present three decomposition theorems: Schur’s theorem, Jordan’s theorem, and the singular-value decomposition. Each of these theorems will prove useful later in this book. We first state Schur’s theorem.

The most important special case of Schur’s decomposition theorem is the case where $\mathbf{A}$ is symmetric.

Exercices

1. Let $\mathbf{A}$ be a symmetric $n \times n$ matrix with eigenvalues $\lambda_{1} \leq \lambda_{2} \leq \cdots \leq \lambda_{n}$. Use Theorem 0.13 to prove that

\begin{equation} \lambda_{1} \leq \frac{\mathbf{x}^\mathrm{T} \mathbf{A} \mathbf{x}}{\mathbf{x}^\mathrm{T} \mathbf{x}} \leq \lambda_{n} . \end{equation}

2. Hence show that, for any $m \times n$ matrix $\mathbf{A}$,

\begin{equation} |\mathbf{A} \mathbf{x}| \leq \mu|\mathbf{x}|, \end{equation}

where $\mu^{2}$ denotes the largest eigenvalue of $\mathbf{A}^\mathrm{T} \mathbf{A}$.

3. Let $\mathbf{A}$ be an $m \times n$ matrix of rank $r$. Show that there exists an $n \times(n-r)$ matrix $\mathbf{S}$ such that

\begin{equation} \mathbf{A} \mathbf{S}=0, \quad \mathbf{S}^\mathrm{T} \mathbf{S}=I_{n-r} \end{equation}

4. Let $\mathbf{A}$ be an $m \times n$ matrix of rank $r$. Let $\mathbf{S}$ be a matrix such that $\mathbf{A} \mathbf{S}=0$. Show that $r(\mathbf{S}) \leq n-r$.

15 - The Jordan decomposition #

Schur’s theorem tells us that there exists, for every square matrix $\mathbf{A}$, a unitary (possibly orthogonal) matrix $\mathbf{S}$ which ’transforms’ $\mathbf{A}$ into an upper triangular matrix $\mathbf{M}$ whose diagonal elements are the eigenvalues of $\mathbf{A}$.

Jordan’s theorem similarly states that there exists a nonsingular matrix, say $\mathbf{T}$, which transforms $\mathbf{A}$ into an upper triangular matrix $\mathbf{M}$ whose diagonal elements are the eigenvalues of $\mathbf{A}$. The difference between the two decomposition theorems is that in Jordan’s theorem less structure is put on the matrix $\mathbf{T}$ (nonsingular, but not necessarily unitary) and more structure on the matrix $\mathbf{M}$.

The most important special case of Theorem 0.14 is this theorem.

Exercices

1. Show that $\left(\lambda I_{k}-\mathbf{J}_{k}(\lambda)\right)^{k}=0$ and use this fact to prove Theorem 0.10.
2. Show that Theorem 0.15 remains valid when $\mathbf{A}$ is complex.

16 - The singular value decomposition #

The third important decomposition theorem is the singular-value decomposition.

We see from \eqref{eq:33} and \eqref{eq:34} that the semi-orthogonal matrices $\mathbf{S}$ and $\mathbf{T}$ satisfy

\begin{equation} \mathbf{A} \mathbf{A}^\mathrm{T} \mathbf{S}=\mathbf{S} \boldsymbol{\Lambda}, \quad \mathbf{A}^\mathrm{T} \mathbf{A} \mathbf{T}=\mathbf{T} \boldsymbol{\Lambda} \end{equation}

Hence, $\boldsymbol{\Lambda}$ contains the $r$ nonzero eigenvalues of $\mathbf{A} \mathbf{A}^\mathrm{T}$ (and of $\mathbf{A}^\mathrm{T} \mathbf{A}$ ) and $\mathbf{S}$ (by construction) and $\mathbf{T}$ contain corresponding eigenvectors. A common mistake in applying the singular-value decomposition is to find $\mathbf{S}$, $\mathbf{T}$, and $\boldsymbol{\Lambda}$ from (35). This is incorrect because, given $\mathbf{S}$, $\mathbf{T}$ is not unique. The correct procedure is to find $\mathbf{S}$ and $\boldsymbol{\Lambda}$ from $\mathbf{A} \mathbf{A}^\mathrm{T} \mathbf{S}=\mathbf{S} \boldsymbol{\Lambda}$ and then define $\mathbf{T}=\mathbf{A}^\mathrm{T} \mathbf{S} \boldsymbol{\Lambda}^{-1 / 2}$. Alternatively, we can find $\mathbf{T}$ and $\boldsymbol{\Lambda}$ from $\mathbf{A}^\mathrm{T} \mathbf{A} \mathbf{T}=\mathbf{T} \boldsymbol{\Lambda}$ and define $\mathbf{S}=\mathbf{A} \mathbf{T} \boldsymbol{\Lambda}^{-1 / 2}$.

17 - Further results concerning eigenvalues #

Let us now prove the following five theorems, all of which concern eigenvalues. this theorem deals with the sum and the product of the eigenvalues. this theorem and this theorem discuss the relationship between the rank and the number of nonzero eigenvalues, and this theorem concerns idempotent matrices.

The following example shows that it is indeed possible that $r(\mathbf{A})>r$. Let

\begin{equation} \mathbf{A}=\left(\begin{array}{ll} 1 & -1 \\ 1 & -1 \end{array}\right) \end{equation}

Then $r(\mathbf{A})=1$ and both eigenvalues of $\mathbf{A}$ are zero.

We note that in, the matrix $\mathbf{A}$ is not required to be symmetric. If $\mathbf{A}$ is idempotent and symmetric, then it is positive semidefinite. Since its eigenvalues are only 0 and 1 and its rank equals $r$, it that $\mathbf{A}$ can be written as

\begin{equation} \mathbf{A}=\mathbf{P} \mathbf{P}^{\mathrm{T}}, \quad \mathbf{P}^{\mathrm{T}} \mathbf{P}=\mathbf{I}_{r} \end{equation}

Exercises

1. The only nonsingular idempotent matrix is the identity matrix.
2. The only idempotent matrix whose eigenvalues are all zero is the null matrix.
3. If $\mathbf{A}$ is a positive semidefinite $n \times n$ matrix with $r(\mathbf{A})=r$, then there exists an $n \times r$ matrix $\mathbf{P}$ such that

\begin{equation} \mathbf{A}=\mathbf{P} \mathbf{P}^{\mathrm{T}}, \quad \mathbf{P}^{\mathrm{T}} \mathbf{P}=\mathbf{\Lambda} \end{equation}

where $\mathbf{\Lambda}$ is an $r \times r$ diagonal matrix containing the positive eigenvalues of $\mathbf{A}$.

Positive (semi)definite matrices #

Positive (semi)definite matrices were introduced in Section 1.6. We have already seen that $\mathbf{A} \mathbf{A}^{\mathrm{T}}$ and $\mathbf{A}^{\mathrm{T}} \mathbf{A}$ are both positive semidefinite and that the eigenvalues of a positive (semi)definite matrix are all positive (nonnegative). We now present some more properties of positive (semi)definite matrices.

For two symmetric matrices $\mathbf{A}$ and $\mathbf{B}$, we shall write $\mathbf{A} \geq \mathbf{B}$ (or $\mathbf{B} \leq \mathbf{A}$ ) if $\mathbf{A}-\mathbf{B}$ is positive semidefinite, and $\mathbf{A}>\mathbf{B}$ (or $\mathbf{B}<\mathbf{A}$ ) if $\mathbf{A}-\mathbf{B}$ is positive definite.

A useful special case of Theorem 0.25 is this theorem.

Three further results for positive definite matrices #

Let us now prove this theorem.

An immediate consequence of Theorem 0.27, proved by induction, is the following.

Another consequence of Theorem 0.27 is this theorem.

Note. The $k \times k$ matrix $\mathbf{A}_{k}$ is obtained from $\mathbf{A}$ by deleting the last $n-k$ rows and columns of $\mathbf{A}$. Notice that $\mathbf{A}_{n}=\mathbf{A}$.

Exercises

1. If $\mathbf{A}$ is positive definite show that the matrix

\begin{equation} \left(\begin{array}{cc} \mathbf{A} & \mathbf{b} \\ \mathbf{b}^{\mathrm{T}} & \mathbf{b}^{\mathrm{T}} \mathbf{A}^{-1} \mathbf{b} \end{array}\right) \end{equation}

is positive semidefinite and singular, and find the eigenvector associated with the zero eigenvalue.

2. Hence show that, for positive definite $\mathbf{A}$,

\begin{equation} \mathbf{x}^{\mathrm{T}} \mathbf{A} \mathbf{x}-2 \mathbf{b}^{\mathrm{T}} \mathbf{x} \geq-\mathbf{b}^{\mathrm{T}} \mathbf{A}^{-1} \mathbf{b} \end{equation}

for every $\mathbf{x}$, with equality if and only if $\mathbf{x}=\mathbf{A}^{-1} \mathbf{b}$.

A useful result #

If $\mathbf{A}$ is a positive definite $n \times n$ matrix, then, in accordance with Theorem 0.28,

\begin{equation} |\mathbf{A}|=\prod_{i=1}^{n} a_{ii} \label{eq:diagonal_det} \end{equation}

if and only if $\mathbf{A}$ is diagonal. If $\mathbf{A}$ is merely symmetric, then \eqref{eq:diagonal_det}, while obviously necessary, is no longer sufficient for the diagonality of $\mathbf{A}$. For example, the matrix

\begin{equation} \mathbf{A}=\left(\begin{array}{lll} 2 & 3 & 3 \\ 3 & 2 & 3 \\ 3 & 3 & 2 \end{array}\right) \end{equation}

has determinant $|\mathbf{A}|=8$ (its eigenvalues are $-1,-1$, and 8 ), thus satisfying \eqref{eq:diagonal_det}, but $\mathbf{A}$ is not diagonal.

this theorem gives a necessary and sufficient condition for the diagonality of a symmetric matrix.

Symmetric matrix functions #

Let $\mathbf{A}$ be a square matrix of order $n \times n$. The $\operatorname{trace} \operatorname{tr} \mathbf{A}$ and the determinant $|\mathbf{A}|$ are examples of scalar functions of $\mathbf{A}$. We can also consider matrix functions, for example, the inverse $\mathbf{A}^{-1}$. The general definition of a matrix function is somewhat complicated, but for symmetric matrices it is easy. So, let us assume that $\mathbf{A}$ is symmetric.

We known from that any symmetric $n \times n$ matrix $\mathbf{A}$ can be diagonalized, which means that there exists an orthogonal matrix $\mathbf{S}$ and a diagonal matrix $\mathbf{\Lambda}$ (containing the eigenvalues of $\mathbf{A}$ ) such that $\mathbf{S}^{\mathrm{T}} \mathbf{A} \mathbf{S}=\mathbf{\Lambda}$. Let $\lambda_{i}$ denote the $i$ th diagonal element of $\mathbf{\Lambda}$ and let $\phi$ be a function so that $\phi(\lambda)$ is defined, for example, $\phi(\lambda)=\sqrt{\lambda}$ or $1 / \lambda$ or $\log \lambda$ or $e^{\lambda}$.

We now define the matrix function $F$ as

\begin{equation} F(\mathbf{\Lambda})=\left(\begin{array}{cccc} \phi\left(\lambda_{1}\right) & 0 & \ldots & 0 \\ 0 & \phi\left(\lambda_{2}\right) & \ldots & 0 \\ \vdots & \vdots & & \vdots \\ 0 & 0 & \ldots & \phi\left(\lambda_{n}\right) \end{array}\right), \end{equation}

and then

\begin{equation} F(\mathbf{A})=\mathbf{S} F(\mathbf{\Lambda}) \mathbf{S}^{\mathrm{T}} \end{equation}

For example, if $\mathbf{A}$ is nonsingular then all $\lambda_{i}$ are nonzero, and letting $\phi(\lambda)=$ $1 / \lambda$, we have

\begin{equation} F(\mathbf{\Lambda})=\mathbf{\Lambda}^{-1}=\left(\begin{array}{cccc} 1 / \lambda_{1} & 0 & \ldots & 0 \\ 0 & 1 / \lambda_{2} & \ldots & 0 \\ \vdots & \vdots & & \vdots \\ 0 & 0 & \ldots & 1 / \lambda_{n} \end{array}\right) \end{equation}

and hence $\mathbf{A}^{-1}=\mathbf{S} \mathbf{\Lambda}^{-1} \mathbf{S}^{\mathrm{T}}$. To check, we have

\begin{equation} \mathbf{A} \mathbf{A}^{-1}=\mathbf{S} \mathbf{\Lambda} \mathbf{S}^{\mathrm{T}} \mathbf{S} \mathbf{\Lambda}^{-1} \mathbf{S}^{\mathrm{T}}=\mathbf{S} \mathbf{\Lambda} \mathbf{\Lambda}^{-1} \mathbf{S}^{\mathrm{T}}=\mathbf{S} \mathbf{S}^{\mathrm{T}}=\mathbf{I}_{n} \end{equation}

as we should. Similarly, if $\mathbf{A}$ is positive semidefinite, then $\mathbf{A}^{1 / 2}=\mathbf{S} \mathbf{\Lambda}^{1 / 2} \mathbf{S}^{\mathrm{T}}$ and

$$ \mathbf{A}^{1 / 2} \mathbf{A}^{1 / 2}=\mathbf{S} \boldsymbol{\Lambda}^{1 / 2} \mathbf{S}^{\mathrm{T}} \mathbf{S} \boldsymbol{\Lambda}^{1 / 2} \mathbf{S}^{\mathrm{T}}=\mathbf{S} \boldsymbol{\Lambda}^{1 / 2} \boldsymbol{\Lambda}^{1 / 2} \mathbf{S}^{\mathrm{T}}=\mathbf{S} \boldsymbol{\Lambda} \mathbf{S}^{\mathrm{T}}=\mathbf{A}, $$

again as it should be. Also, when $\mathbf{A}$ is positive definite (hence nonsingular), then $\mathbf{A}^{-1 / 2}=\mathbf{S} \boldsymbol{\Lambda}^{-1 / 2} \mathbf{S}^{\mathrm{T}}$ and

$$ \begin{aligned} \left(\mathbf{A}^{1 / 2}\right)^{-1} & =\left(\mathbf{S} \boldsymbol{\Lambda}^{1 / 2} \mathbf{S}^{\mathrm{T}}\right)^{-1}=\mathbf{S}\left(\boldsymbol{\Lambda}^{1 / 2}\right)^{-1} \mathbf{S}^{\mathrm{T}}=\mathbf{S}\left(\boldsymbol{\Lambda}^{-1}\right)^{1 / 2} \mathbf{S}^{\mathrm{T}} \\ & =\left(\mathbf{S} \boldsymbol{\Lambda}^{-1} \mathbf{S}^{\mathrm{T}}\right)^{1 / 2}=\left(\mathbf{A}^{-1}\right)^{1 / 2} \end{aligned} $$

so that this expression is unambiguously defined. Symmetric matrix functions are thus always defined through their eigenvalues. For example, the logarithm or exponential of $\mathbf{A}$ is not the matrix with elements $\log a_{i j}$ or $e^{a_{i j}}$, but rather a matrix whose eigenvalues are $\log \lambda_{i}$ or $e^{\lambda_{i}}$ and whose eigenvectors are the same as the eigenvectors of $\mathbf{A}$. This is similar to the definition of a positive definite matrix, which is not a matrix all whose elements are positive, but rather a matrix all whose eigenvalues are positive.

Miscellaneous exercises #

Exercises

1. If $\mathbf{A}$ and $\mathbf{B}$ are square matrices such that $\mathbf{A}\mathbf{B}=0, \mathbf{A} \neq 0, \mathbf{B} \neq 0$, then prove that $|\mathbf{A}|=|\mathbf{B}|=0$.
2. If $\mathbf{x}$ and $\mathbf{y}$ are vectors of the same order, prove that $\mathbf{x}^{\mathrm{T}} \mathbf{y}=\operatorname{tr} \mathbf{y} \mathbf{x}^{\mathrm{T}}$.
3. Let

$$ \mathbf{A}=\left(\begin{array}{ll} \mathbf{A}_{11} & \mathbf{A}_{12} \\ \mathbf{A}_{21} & \mathbf{A}_{22} \end{array}\right) $$

Show that

$$ |\mathbf{A}|=\left|\mathbf{A}_{11}\right|\left|\mathbf{A}_{22}-\mathbf{A}_{21} \mathbf{A}_{11}^{-1} \mathbf{A}_{12}\right| $$

if $\mathbf{A}_{11}$ is nonsingular, and

$$ |\mathbf{A}|=\left|\mathbf{A}_{22}\right|\left|\mathbf{A}_{11}-\mathbf{A}_{12} \mathbf{A}_{22}^{-1} \mathbf{A}_{21}\right| $$

if $\mathbf{A}_{22}$ is nonsingular. 4. Show that $(\mathbf{I}-\mathbf{A}\mathbf{B})^{-1}=\mathbf{I}+\mathbf{A}(\mathbf{I}-\mathbf{B}\mathbf{A})^{-1}\mathbf{B}$, if the inverses exist. 5. Show that

$$ (\alpha \mathbf{I}-\mathbf{A})^{-1}-(\beta \mathbf{I}-\mathbf{A})^{-1}=(\beta-\alpha)(\beta \mathbf{I}-\mathbf{A})^{-1}(\alpha \mathbf{I}-\mathbf{A})^{-1} . $$

6. If $\mathbf{A}$ is positive definite, show that $\mathbf{A}+\mathbf{A}^{-1}-2 \mathbf{I}$ is positive semidefinite.
7. For any symmetric matrices $\mathbf{A}$ and $\mathbf{B}$, show that $\mathbf{A}\mathbf{B}-\mathbf{B}\mathbf{A}$ is skewsymmetric.
8. Let $\mathbf{A}$ and $\mathbf{B}$ be two $m \times n$ matrices of rank $r$. If $\mathbf{A}\mathbf{A}^{\mathrm{T}}=\mathbf{B}\mathbf{B}^{\mathrm{T}}$ then $\mathbf{A}=\mathbf{B}\mathbf{Q}$, where $\mathbf{Q}\mathbf{Q}^{\mathrm{T}}$ (and hence $\mathbf{Q}^{\mathrm{T}} \mathbf{Q}$ ) is idempotent of rank $k \geq r$ (Neudecker and van de Velden 2000).
9. Let $\mathbf{A}$ be an $m \times n$ matrix partitioned as $\mathbf{A}=\left(\mathbf{A}_{1}: \mathbf{A}_{2}\right)$ and satisfying $\mathbf{A}_{1}^{\mathrm{T}} \mathbf{A}_{2}=0$ and $r\left(\mathbf{A}_{1}\right)+r\left(\mathbf{A}_{2}\right)=m$. Then, for any positive semidefinite matrix $\mathbf{V}$, we have

$$ r(\mathbf{V})=r\left(\mathbf{A}_{1}\right)+r\left(\mathbf{A}_{2}^{\mathrm{T}} \mathbf{V} \mathbf{A}_{2}\right) \Longleftrightarrow r(\mathbf{V})=r\left(\mathbf{V}: \mathbf{A}_{1}\right) $$

10. Prove that the eigenvalues $\lambda_{i}$ of $(\mathbf{A}+\mathbf{B})^{-1} \mathbf{A}$, where $\mathbf{A}$ is positive semidefinite and $\mathbf{B}$ is positive definite, satisfy $0 \leq \lambda_{i}<1$.
11. Let $\mathbf{x}$ and $\mathbf{y}$ be $n \times 1$ vectors. Prove that $\mathbf{x} \mathbf{y}^{\mathrm{T}}$ has $n-1$ zero eigenvalues and one eigenvalue $\mathbf{x}^{\mathrm{T}} \mathbf{y}$.
12. Show that $\left|\mathbf{I}+\mathbf{x} \mathbf{y}^{\mathrm{T}}\right|=1+\mathbf{x}^{\mathrm{T}} \mathbf{y}$.
13. Let $\mu=1+\mathbf{x}^{\mathrm{T}} \mathbf{y}$. If $\mu \neq 0$, show that $\left(\mathbf{I}+\mathbf{x} \mathbf{y}^{\mathrm{T}}\right)^{-1}=\mathbf{I}-(1 / \mu) \mathbf{x} \mathbf{y}^{\mathrm{T}}$.
14. Show that $\left(\mathbf{I}+\mathbf{A} \mathbf{A}^{\mathrm{T}}\right)^{-1} \mathbf{A}=\mathbf{A}\left(\mathbf{I}+\mathbf{A}^{\mathrm{T}} \mathbf{A}\right)^{-1}$.
15. Show that $\mathbf{A}\left(\mathbf{A}^{\mathrm{T}} \mathbf{A}\right)^{1 / 2}=\left(\mathbf{A} \mathbf{A}^{\mathrm{T}}\right)^{1 / 2} \mathbf{A}$.
16. (Monotonicity of the entropic complexity.) Let $\mathbf{A}_{n}$ be a positive definite $n \times n$ matrix and define

$$ \phi(n)=\frac{n}{2} \log \operatorname{tr}\left(\mathbf{A}_{n} / n\right)-\frac{1}{2} \log \left|\mathbf{A}_{n}\right| . $$

Let $\mathbf{A}_{n+1}$ be a positive definite $(n+1) \times(n+1)$ matrix such that

$$ \mathbf{A}_{n+1}=\left(\begin{array}{cc} \mathbf{A}_{n} & \mathbf{a}_{n} \\ \mathbf{a}_{n}^{\mathrm{T}} & \alpha_{n} \end{array}\right) $$

Then,

$$ \phi(n+1) \geq \phi(n) $$

with equality if and only if

$$ \mathbf{a}_{n}=0, \quad \alpha_{n}=\operatorname{tr} \mathbf{A}_{n} / n $$