P.7 Review of Linear Algebra

Let \(A\) be an \(m\times n\) matrix of real numbers, denoted as \(A\in\mathbb{R}^{m\times n}\). Then \[A = \begin{pmatrix} a_{11} & a_{12}& \dots & a_{1n} \\ a_{21} & a_{22} & \dots & a_{2n} \\ \vdots & & & \vdots \\ a_{m1} & a_{m2} & \dots & a_{mn} \end{pmatrix}.\] Matrix addition is defined element wise for matrices of compatible dimensions as \[\begin{gathered} \underbrace{\begin{pmatrix} a_{11} & a_{12}& \dots & a_{1n} \\ a_{21} & a_{22} & \dots & a_{2n} \\ \vdots & & & \vdots \\ a_{m1} & a_{m2} & \dots & a_{mn} \end{pmatrix}}_{A} + \underbrace{\begin{pmatrix} b_{11} & b_{12}& \dots & b_{1n} \\ b_{21} & b_{22} & \dots & b_{2n} \\ \vdots & & & \vdots \\ b_{m1} & b_{m2} & \dots & b_{mn} \end{pmatrix}}_{B} \\ = \underbrace{\begin{pmatrix} a_{11}+b_{11} & a_{12}+b_{12} & \dots & a_{1n}+a_{1n} \\ a_{21}+b_{21} & a_{22}+b_{22} & \dots & a_{2n}+b_{2n} \\ \vdots & & & \vdots \\ a_{m1}+b_{m1} & a_{m2}+b_{m2} & \dots & a_{mn}+b_{mn} \end{pmatrix}}_{C}. \end{gathered}\] To multiply a matrix times a vector, the inner dimensions must match: \[\underbrace{A}_{m\times n}\underbrace{x}_{n\times 1} = \begin{pmatrix} a_{11} & \dots & a_{1n} \\ \vdots && \vdots \\ a_{m1} & \dots & a_{mn} \end{pmatrix} \begin{pmatrix} x_1 \\ \vdots \\ x_n\end{pmatrix} = \begin{pmatrix} \sum_{i=1}^n a_{1i}x_i \\ \vdots \\ \sum_{i=1}^n a_{mi}x_i \end{pmatrix} = \underbrace{b}_{m\times 1}.\] For example, \[\begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} \begin{pmatrix} 5 \\ 6 \end{pmatrix} = \begin{pmatrix} 17 \\ 39 \end{pmatrix}.\] Multiplying two matrices also requires matching dimensions: \[\begin{aligned} \underbrace{A}_{m\times n} \underbrace{B}_{n\times p} &= \begin{pmatrix} a_{11} & \dots & a_{1n} \\ \vdots && \vdots \\ a_{m1} & \dots & a_{mn} \end{pmatrix} \begin{pmatrix} b_{11} & \dots & b_{1n} \\ \vdots && \vdots \\ b_{m1} & \dots & b_{mn} \end{pmatrix} \\ &= \begin{pmatrix} \sum_{i=1}^n a_{1i}b_{i1} & \dots & \sum_{i=1}^n a_{1i}b_{ip} \\ \vdots && \vdots \\ \sum_{i=1}^n a_{mi}b_{i1} & \dots & \sum_{i=1}^n a_{mi}b_{ip}\end{pmatrix} = \underbrace{C}_{m\times p}. \end{aligned}\] Note that if \(A\in\mathbb{R}^{m\times n}\) and \(B\in\mathbb{R}^{n\times p}\), then \(AB\) is a valid product, but \(BA\) is not a valid product. Even if the dimensions are compatible, i.e., if \(A\) and \(B\) are square, in general \[AB \neq BA.\]

P.7.1 Transpose

If \(A\in\mathbb{R}^{m\times n}\), then the transpose of \(A\), denoted as \(A^{\top}\in\mathbb{R}^{n\times m}\) is obtained by interchanging the rows and the columns. For example \[\begin{aligned} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix}^\top &= \begin{pmatrix} x_1 & x_2 & x_3 \end{pmatrix}, \\ \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}^{\top} &= \begin{pmatrix} 1 & 3 \\ 2 & 4 \end{pmatrix}. \end{aligned}\] A square matrix \(A\) is said to be symmetric if \(A^\top=A\). Similarly, \(A\) is said to be skew-symmetric if \(A^\top=-A\). Every square matrix \(A\in\mathbb{R}^{n\times n}\) can be decomposed into the sum of a symmetric and a skew-symmetric matrix as \[\begin{aligned} A &= \frac{1}{2}A + \frac{1}{2}A + \frac{1}{2}A^\top - \frac{1}{2}A^\top \\ &= \left(\frac{1}{2}A + \frac{1}{2}A^\top\right) + \left(\frac{1}{2}A-\frac{1}{2}A^\top\right) \\ & = A_s + A_{ss}, \end{aligned}\] where \(A_s=\frac{1}{2}(A+A^\top)\) is symmetric, and \(A_{ss}=\frac{1}{2}(A-A^\top)\) is skew-symmetric.

The following properties are easily verified by direct manipulation: \[\begin{aligned} (AB)^\top &= B^\top A^\top \\ (A+B)^\top &= A^\top + B^\top. \end{aligned}\]

P.7.2 Trace

The trace operator is defined for square matrices. If \(A\in\mathbb{R}^{n\times n}\), then \[\text{tr}(A) = \sum_{i=1}^n a_{ii},\] or in other words, the sum of the diagonals of \(A\). For example \[\text{tr}\begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} = 1+4 = 5.\]

P.7.3 Determinant

The determinant operator is defined for square matrices \(A\in\mathbb{R}^{n\times n}\) as \[\det(A) = \sum_{j=1}^n a_{ij}\gamma_{ij},\] for any \(i=1,\dots,n\), where the co-factor \[\gamma_{ij} = (-1)^{(i+j)}\det(M_{ij})\] and where the minor \(M_{ij}\) is the \((n-1)\times(n-1)\) matrix obtained by removing the \(i^{th}\) row and the \(j^{th}\) column of \(A\). As an example, \[\begin{aligned} \det\begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 0 \\ 6 & 7 & 8\end{pmatrix} &= 1\cdot\det\begin{pmatrix} 5 & 0 \\ 7 & 8\end{pmatrix} - 2\cdot\det\begin{pmatrix} 4 & 0 \\ 6 & 8 \end{pmatrix} \\ &\qquad + 3\cdot\det\begin{pmatrix} 4 & 5 \\ 6 & 7 \end{pmatrix} \\ &= 1\cdot(5\cdot 8 - 7\cdot 0) - 2\cdot(4\cdot 8 - 6\cdot 0) \\ &\qquad + 3\cdot(4\cdot 7 - 6\cdot 5) \\ &= -30. \end{aligned}\] The adjugate of \(A\) is defined as the transpose of the co-factors of \(A\): \[\text{adj}(A) = \begin{pmatrix} \gamma_{11} & \dots & \gamma_{n1} \\ \vdots & & \vdots \\ \gamma_{1n} & \dots & \gamma_{nn}\end{pmatrix}.\] We have the following properties for the determinant: \[\begin{aligned} \det(A) &= \det(A^\top) \\ \det(AB) &= \det(A)\det(B) \\ \det(A^{-1}) &= \frac{1}{\det(A)}. \end{aligned}\]

There are also well defined rules for finding the determinant of a block matrix. Let \[E = \begin{pmatrix} A & B \\ C & D \end{pmatrix}\] where \(A\in\mathbb{R}^{n\times n}\), \(B\in\mathbb{R}^{n\times p}\), \(C\in\mathbb{R}^{m\times n}\) and \(D\in\mathbb{R}^{m\times m}\), then it can be shown that if \(A\) is invertible, then \[\det(E) = \det(A) \det\left(D-CA^{-1}B\right).\] As a special case, if either \(B=0\) or \(C=0\), then \[\det(E) = \det(A)\det(D).\] For example, \[\det\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 4 & 5 & 6 \\ 3 & 4 & 5 & 6 & 7 \\ 0 & 0 & 0 & 8 & 9 \\ 0 & 0 & 0 & 9 & 10 \end{pmatrix} = \det\begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 4 \\ 3 & 4 & 5 \end{pmatrix} \cdot\det\begin{pmatrix} 8 & 9 \\ 9 & 10 \end{pmatrix}.\]

P.7.4 Matrix Inverses

If \(A\in\mathbb{R}^{n\times n}\), and there exists a matrix \(B\in\mathbb{R}^{n\times n}\) such that \[AB = BA = I,\] then \(B\) is said to be the inverse of \(A\) and is denoted as \(B=A^{-1}\).

The inverse of any square matrix can be expressed in terms of its adjugate and its determinant as \[A^{-1} = \frac{\text{adj}(A)}{\text{det}(A)}.\] For a \(2\times 2\) matrix we have the simple formula \[\begin{pmatrix} a & b \\ c & d \end{pmatrix}^{-1} =\frac{\text{adj}\begin{pmatrix} a & b \\ c & d\end{pmatrix}}{\text{det}\begin{pmatrix} a & b \\ c & d \end{pmatrix}}= \frac{\begin{pmatrix} d & -b \\ -c & a\end{pmatrix}}{ad-bc}.\] If \(\det(A)\neq 0\), then \(A\) is called non-singular.

If \(A\) and \(B\) are nonsingular, then \[(AB)^{-1} = B^{-1}A^{-1}.\]

For block matrices it can be verified by direct substitution that \begin{align} \begin{pmatrix} A & B \\ C & D \end{pmatrix}^{-1} &= \begin{pmatrix} (A-BD^{-1}C)^{-1} & -(A-BD^{-1}C)^{-1}BD^{-1} \\ -D^{-1}C(A-BD^{-1}C)^{-1} & D^{-1}+D^{-1}C(A-BD^{-1}C)^{-1}BD^{-1} \end{pmatrix} \tag{P.7.1}\\ &= \begin{pmatrix} A^{-1}+A^{-1}B(D-CA^{-1}B)^{-1}CA^{-1} & -A^{-1}B(D-CA^{-1}B)^{-1} \\ -(D-CA^{-1}B)^{-1}CA^{-1} & (D-CA^{-1}B)^{-1} \end{pmatrix}, \tag{P.7.2} \end{align} from which we get the famous matrix inversion lemma \[\tag{P.7.3} (A-BD^{-1}C)^{-1} = A^{-1}+A^{-1}B(D-CA^{-1}B)^{-1}CA^{-1}.\] When \(C=0\) we get the simple formula \[\begin{pmatrix} A & B \\ 0 & D\end{pmatrix}^{-1} = \begin{pmatrix} A^{-1} & -A^{-1}BD^{-1} \\ 0 & D^{-1} \end{pmatrix}.\]

P.7.5 Eigenvalues and Eigenvectors

The pair \((\lambda, v)\) where \(\lambda \in \mathbb{C}\) and \(0\neq v\in\mathbb{C}^{n\times 1}\) is said to be an eigenvalue-eigenvector pair of the matrix \(A\in\mathbb{R}^{n\times n}\) if \[Av = \lambda v.\] The following statements are equivalent:

  1. \((\lambda, v)\) is an eigenvalue-eigenvector pair of \(A\),

  2. \(Av = \lambda v\),

  3. \((\lambda I - A)v = 0\), where \(I\) is the \(n\times n\) identity matrix,

  4. \(v\) is in the null space of \((\lambda I - A)\),

  5. \(\det(\lambda I-A)=0\).

For example, to find the eigenvalues and eigenvectors of \[A = \begin{pmatrix} 0 & 1 \\ -2 & -3 \end{pmatrix},\] first compute \[\begin{aligned} \det(\lambda I - A) &= \det\begin{pmatrix} \lambda & -1 \\ 2 & \lambda+3 \end{pmatrix} \\ &= \lambda^2 + 3\lambda + 2 = (\lambda+2)(\lambda+1). \end{aligned}\] Setting \(\det(\lambda I - A)=0\) implies that the eigenvalues are \[\lambda_1 = -2, \qquad \lambda_2 = -1.\] To find the eigenvector associated with \(\lambda_1\) we need to find a vector \(v_1\) that is in the null space of \((\lambda_1 I -A)\). Since \[(\lambda_1 I - A)v_1 = \begin{pmatrix} -2 & -1 \\ 2 & 1 \end{pmatrix}\begin{pmatrix} v_{11} \\ v_{12} \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix},\] we have that \(2v_{11}=-v_{12}\). Therefore, \(v_1 = (1, -2)^\top\) is in the null space of \((\lambda_1 I -A)\) and is an eigenvector of \(A\) associated with eigenvalue \(\lambda_1\).

To find the eigenvector associated with \(\lambda_2\) we need to find a vector \(v_2\) that is in the null space of \((\lambda_2 I -A)\). Since \[(\lambda_2 I - A)v_2 = \begin{pmatrix} -1 & -1 \\ 2 & 2 \end{pmatrix}\begin{pmatrix} v_{21} \\ v_{22} \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix},\] we have that \(v_{21}=-v_{22}\). Therefore, \(v_2 = (-1, 1)^\top\) is in the null space of \((\lambda_2 I -A)\) and is an eigenvector of \(A\) associated with eigenvalue \(\lambda_2\).

Since \(Av_1=\lambda_1 v_1\) and \(Av_2=\lambda_2 v_2\) we can write \[A\begin{pmatrix}v_1 & v_2\end{pmatrix} = \begin{pmatrix}v_1 & v_2\end{pmatrix} \begin{pmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{pmatrix}.\] Defining \(M = \begin{pmatrix} v_1 & v_2 \end{pmatrix}\) and \(\Lambda = \begin{pmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{pmatrix}\) we have \[AM = M\Lambda.\] When \(M\) is invertible, we have \[A = M\Lambda M^{-1}.\] \(M\) will always be invertible when the eigenvalues are distinct. For example, it can be verified that \[\begin{pmatrix} 0 & 1 \\ -2 & -3 \end{pmatrix} = \begin{pmatrix} 1 & -1 \\ -2 & 1 \end{pmatrix} \begin{pmatrix} -2 & 0 \\ 0 & 11 \end{pmatrix} \begin{pmatrix} 1 & -1 \\ -2 & 1 \end{pmatrix}^{-1}.\] The formula \(A=M\Lambda M^{-1}\) is called the eigen-decomposition of \(A\).

The trace and the determinant of \(A\) can be written in terms of the eigenvalues of \(A\) as \[\begin{aligned} \text{tr}(A) &= \sum_{i=1}^n \lambda_i(A), \\ \det(A) &= \Pi_{i=1}^n \lambda_i(A). \end{aligned}\] where \(\lambda_i(A)\) is the \(i^{th}\) eigenvalue of \(A\).

P.7.6 Linear Independence and Rank

The vectors \(x_1, x_2, \dots, x_p\in\mathbb{R}^{n\times 1}\) are said to be linearly independent if \[c_1 x_1 + c_2 x_2 + \dots + c_px_p=0,\] implies that \(c_1=c_2=\dots=c_p=0\). For example, the vectors \((1,0)^\top\) and \((0,1)^\top\) are linearly independent since \[c_1\begin{pmatrix} 1 \\ 0 \end{pmatrix} + c_2\begin{pmatrix} 0 \\ 1 \end{pmatrix} = \begin{pmatrix} c_1 \\ c_2 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}\] implies that \(c_1=c_2=0\). Alternatively, the vectors \((1,0)^\top\) and \((3, 0)^\top\) are not linearly independent since \[c_1\begin{pmatrix} 1 \\ 0 \end{pmatrix} + c_2\begin{pmatrix} 3 \\ 0 \end{pmatrix} = \begin{pmatrix} c_1+3c_0 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}\] is true if \(c_1=-3c_2\) for any \(c_2\).

The rank of a matrix is defined to be the number of linearly independent rows or columns. For example \[\begin{aligned} \text{rank}\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} &= 2 \\ \text{rank}\begin{pmatrix} 1 & 3 \\ 0 & 0 \end{pmatrix} &= 1. \end{aligned}\]

P.7.7 Special Matrices

The matrix \(A\in\mathbb{R}^{n\times n}\) is said to be diagonal if \[A = \begin{pmatrix} a_{11} & 0 & \dots & 0 \\ 0 & a_{22} & \dots & 0 \\ \vdots & & \ddots & \vdots \\ 0 & 0 & \dots & a_{nn} \end{pmatrix}.\] For example, \[A = \begin{pmatrix} 2 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 \\ 0 & 0 & 4 & 0 \\ 0 & 0 & 0 & 5 \end{pmatrix}\] is a diagonal matrix.

The matrix \(A\in\mathbb{R}^{n\times n}\) is said to be upper triangular if \[A = \begin{pmatrix} a_{11} & a_{12} & \dots & a_{1n} \\ 0 & a_{22} & \dots & a_{2n} \\ \vdots & & \ddots & \vdots \\ 0 & 0 & \dots & a_{nn} \end{pmatrix}.\] For example, \[A = \begin{pmatrix} 2 & 3 & 4 & 5 \\ 0 & 6 & 7 & 8 \\ 0 & 0 & 9 & 10 \\ 0 & 0 & 0 & 11 \end{pmatrix}\] is an upper triangular matrix.

The matrix \(A\in\mathbb{R}^{n\times n}\) is said to be in upper companion form if \[A = \begin{pmatrix} -a_1 & -a_2 & \dots & -a_{n-1} & -a_n \\ 1 & 0 & \dots & 0 & 0 \\ \vdots & \ddots & & \vdots & 0 \\ 0 & 0 & \dots & 1 & 0 \end{pmatrix}.\] For example, \[A = \begin{pmatrix} -2 & -3 & -4 & -5 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix}\] is in upper companion form.

The matrix \(A\in\mathbb{R}^{n\times n}\) is said to be a Vandermonde matrix if \[A = \begin{pmatrix} 1 & a_1 & a_1^2 & \dots & a_1^{n-1} \\ 1 & a_2 & a_2^2 & \dots & a_2^{n-1} \\ 1 & a_3 & a_3^2 & \dots & a_3^{n-1} \\ 1 & a_4 & a_4^2 & \dots & a_4^{n-1} \end{pmatrix}.\] For example, \[A = \begin{pmatrix} 1 & 2 & 4 & 9 \\ 1 & 3 & 9 & 27 \\ 1 & 4 & 16 & 64 \\ 1 & 5 & 25 & 125 \end{pmatrix}\] is a Vandermonde matrix.