Matrix Theory Note

Matrix Theory

Basic Theories

Matrix

Definition

$A_{m\times n}=\left[\begin{array}{ccc}{a}_{11}& \dots & a_{1n}\\ ⋮& \ddots & ⋮\\ a_{m1}& \dots & a_{mn}\end{array}\right]$

Operations

Addition, Subtraction

$A_{m\times n}\pm B_{m\times n}=\left[\begin{array}{ccc}{a}_{11}\pm b_{11}& \dots & a_{1n}\pm b_{1n}\\ ⋮& \ddots & ⋮\\ a_{m1}\pm b_{m1}& \dots & a_{mn}\pm b_{mn}\end{array}\right]$

Scalar Multiplication

$k{A}_{m\times n}=\left[\begin{array}{ccc}k{a}_{11}& \dots & k{a}_{1n}\\ ⋮& \ddots & ⋮\\ k{a}_{m1}& \dots & k{a}_{mn}\end{array}\right]$

Transpose

$A^{⊺}$ $a_{ij}\stackrel{⊺}{\to }{a}_{ji}$, $A_{m\times n}\stackrel{\top }{\to }{A}_{n\times m}$

Trace

Determinant

Matrix Multiplication

$A_{m\times p}\cdot B_{p\times n}=\left[\begin{array}{ccc}{a}_{11}& \dots & a_{1p}\\ ⋮& \ddots & ⋮\\ a_{m1}& \dots & a_{mp}\end{array}\right]\left[\begin{array}{ccc}{b}_{11}& \dots & b_{1n}\\ ⋮& \ddots & ⋮\\ b_{p1}& \dots & b_{pn}\end{array}\right]={\left[\begin{array}{ccc}{a}_{11}+b_{11}+\cdots +a_{1p}+b_{p1}& \dots & a_{11}+b_{1n}+\cdots +a_{1p}+b_{pn}\\ ⋮& \ddots & ⋮\\ a_{m1}+b_{11}+\cdots +a_{mp}+b_{p1}& \dots & a_{m1}+b_{1n}+\cdots +a_{mp}+b_{pn}\end{array}\right]}_{m\times n}$ $A_i^{⊺}\cdot B_j={\sum }_{k=1}^p{a}_{ik}\cdot b_{kj}=c_{ij}$ where $1\le i\le m$, $1\le j\le n$

Vector-Matrix Multiplication

$A\mathbf{x}=[A_1,A_2,\dots ,A_n][x_1,x_2,\dots ,x_n{]}^{⊺}=x_1{A}_1+x_2{A}_2+\cdots +x_n{A}_n={\sum }_{k=1}^n{x}_k{A}_k$

Link to original

Trace

Definition

$\mathrm{tr}(A)={\sum }_{i=1}^n{a}_{ii}=a_{11}+a_{22}+\cdots +a_{nn}$

The sum of elements on the main diagonal

Facts

$\mathrm{tr}(A+B)=\mathrm{tr}(A)+\mathrm{tr}(B)$

$\mathrm{tr}(cA)=c\mathrm{tr}(A)$

$\mathrm{tr}(A^{⊺})=\mathrm{tr}(A)$

$\mathrm{tr}(AB)=\mathrm{tr}(BA)$

$\mathrm{tr}(A{B}^{⊺})=\mathrm{tr}(B{A}^{⊺})$

$\mathrm{tr}(ABCD)=\mathrm{tr}(BCDA)=\mathrm{tr}(CDAB)=\mathrm{tr}(DABC)$^[Cyclic property]

$\mathrm{tr}(\mathbf{A})={\sum }_{i=1}^n{\lambda }_i$ The Trace of the matrix is equal to the sum of the eigenvalues of the matrix.

Proof Since the matrix $\mathbf{A}-\lambda \mathbf{I}$ only has $\lambda$ term on diagonal, and the calculation of cofactor deletes a row and a column, the coefficient of ${\lambda }^{n-1}$ of $\text{det}(\mathbf{A}-\lambda \mathbf{I})$ is always $-(a_{11}+a_{22}+\cdots +a_{nn})$. Also, since ${\lambda }_i$ are the solution of the Characteristic Polynomial, the expression is factorized as $\text{det}(\mathbf{A}-\lambda \mathbf{I})=(\lambda -{\lambda }_1)(\lambda -{\lambda }_2)\dots (\lambda -{\lambda }_n)$ and the coefficient of ${\lambda }^{n-1}$ become a $-({\lambda }_1+{\lambda }_2+\cdots +{\lambda }_n)$ Therefore, $-(a_{11}+a_{22}+\cdots +a_{nn})=-({\lambda }_1+{\lambda }_2+\cdots +{\lambda }_n)$ and $\text{Trace}(\mathbf{A})={\sum }_{i=1}^n{\lambda }_i$.

Link to original

Link to original

Determinant

Definition

$\text{det}(\mathbf{A})=|\mathbf{A}|$

Computation

$2\times 2$ matrix

$\left|\begin{array}{cc}a& b\\ c& d\end{array}\right|=ad-bc$

$n\times n$ matrix

Laplace Expansion

Definition

Let $C$ be a cofactor matrix of $\mathbf{A}$

Along the $j$th column gives

$\text{det}(\mathbf{A})={\sum }_{i=1}^n{a}_{ij}{C}_{ij}={\sum }_{i=1}^n{a}_{ij}(-1{)}^{i+j}{M}_{i,j}$

Along the $i$th row gives

$\text{det}(\mathbf{A})={\sum }_{j=1}^n{a}_{ij}{C}_{ij}={\sum }_{j=1}^n{a}_{ij}(-1{)}^{i+j}{M}_{i,j}$

Link to original

Facts

$\text{det}\mathbf{A}\ne 0\iff \exists {\mathbf{A}}^{-1}$ $\text{det}\mathbf{A}=0\iff \nexists {\mathbf{A}}^{-1}$

The volume of box^[parallelepiped] $\in {\mathbb{R}}^n$ is expressed by a determinant

$\text{det}(\mathbf{I})=1$

$\text{det}(\mathbf{A})$ changes sign, when two rows are exchanged (permutated)

$\text{det}(\mathbf{A})$ depends on linearly on the 1st row.

$\text{det}(t\mathbf{A})=t^n\text{det}(\mathbf{A})$

$\text{det}(\mathbf{AB})=\text{det}(\mathbf{A})\text{det}(\mathbf{B})$

If two row or column vectors in $\mathbf{A}$ are equal, then $\text{det}(\mathbf{A})=0$

Gauss Elimination does not change $\text{det}(\mathbf{A})$

If a matrix $\mathbf{A}$ has zero row or column vectors, then $\text{det}(\mathbf{A})=0$

If a matrix $\mathbf{A}$ is diagonal or triangular, then the determinant of $\mathbf{A}$ is the product of diagonal elements $\text{det}(\mathbf{A})={\prod }_{i=1}^n{a}_{ii}$ where $a_{ii}$ is the $i,i$ element of the matrix $\mathbf{A}$.

$\text{det}({\mathbf{A}}^{-1})=\text{det}(\mathbf{A}{)}^{-1}$

$\text{det}({\mathbf{A}}^{⊺})=\text{det}(\mathbf{A})$

$|\mathbf{A}|={\prod }_{i=1}^n{\lambda }_i$ The Determinant of the matrix is equal to the product of the eigenvalues of the matrix.

Link to original

$|I_m+AB|=|I_n+BA|$ where the dimensions of the matrices are $m\times n$ and $n\times m$ respectively.

$|A\pm \mathbf{u}{\mathbf{u}}^{⊺}|=|A|(1\pm {\mathbf{u}}^{⊺}{A}^{-1}\mathbf{u})$

Link to original

Idempotent Matrix

Definition

$A^2=A$ A matrix whose squared matrix is itself.

Facts

Eigenvalues of idempotent matrix is either $0$ or $1$.

Let $A$ be a symmetric matrix. Then, $A$ has $r$ eigenvalues equal to $1$ and the rest zero $\iff A^2=A,\mathrm{rank}(A)=r$.

Let $A$ be an idempotent matrix, then $\mathrm{rank}(A)=\mathrm{tr}(A)$

If $A$ is idempotent, then $I-A$ also idempotent.

Link to original

Inverse Matrix

Rank of Matrix

Definition

$\mathrm{rank}(\mathbf{A})$

The rank of matrix is the number of linearly independent column vectors, or the number of non-zero pivots in Gauss Elimination

Facts

$\mathrm{rank}(AB)\le \min (\mathrm{rank}(A),\mathrm{rank}(B))$

For the non-singular matrices $P$ and $Q$, $\mathrm{rank}(PAQ)=\mathrm{rank}(A)$

Rank–Nullity Theorem

$\mathrm{rank}(A)=\mathrm{rank}(A^{⊺})=\mathrm{rank}(A^{⊺}A)=\mathrm{rank}(A{A}^{⊺})$

If a matrix $A$ is Symmetric Matrix, then $\mathrm{rank}(A)$ is the number of non-zero eigenvalues.

Link to original

Inverse Matrix

Definition

${\mathbf{A}}^{-1}$ satisfies $\mathbf{A}{\mathbf{A}}^{-1}={\mathbf{A}}^{-1}\mathbf{A}=\mathbf{I}$ for given matrix $\mathbf{A}$

Computation

2 x 2 matrix

${\mathbf{A}}^{-1}=\frac{1}{|\mathbf{A}|}\left[\begin{array}{cc}d& -b\\ -c& a\end{array}\right]$ where the matrix $\mathbf{A}=\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]$, and $|\mathbf{A}|$ is a Determinant of the matrix

Using Cofactor

$\mathbf{A}\mathrm{adj}(\mathbf{A})={\mathbf{AC}}^{⊺}=\text{det}(\mathbf{A})\mathbf{I}$ where the matrix $\mathbf{C}=\left[\begin{array}{cccc}{C}_{11}& C_{12}& \cdots & C_{1n}\\ C_{21}& C_{22}& \cdots & C_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ C_{n1}& C_{n2}& \cdots & C_{nn}\end{array}\right]$ is the cofactor matrix, which is formed by all the cofactors of a given matrix $\mathbf{A}$. Then, by the definition of inverse matrix, ${\mathbf{A}}^{-1}=\frac{1}{\text{det}(\mathbf{A})}{\mathbf{C}}^{⊺}$

Link to original

Sherman–Morrison Formula

Definition

Suppose $\mathbf{A}\in {\mathbb{R}}^{n\times n}$ is an invertible matrix an d $\mathbf{v},\mathbf{u}\in {\mathbb{R}}^n$. Then, $\mathbf{A}+\mathbf{u}{\mathbf{v}}^{⊺}$ is invertible $\iff 1+{\mathbf{v}}^{⊺}{\mathbf{A}}^{-1}\mathbf{u}\ne 0$. In this case, $(\mathbf{A}+\mathbf{u}{\mathbf{v}}^{⊺}{)}^{-1}={\mathbf{A}}^{-1}-\frac{{\mathbf{A}}^{-1}\mathbf{u}{\mathbf{v}}^{⊺}{\mathbf{A}}^{-1}}{1+{\mathbf{v}}^{⊺}{\mathbf{A}}^{-1}\mathbf{u}}$

Proof

Multiplying $(\mathbf{A}+\mathbf{u}{\mathbf{v}}^{⊺})$ to the RHS gives $\left({\mathbf{A}}^{-1}-\frac{{\mathbf{A}}^{-1}\mathbf{u}{\mathbf{v}}^{⊺}{\mathbf{A}}^{-1}}{1+{\mathbf{v}}^{⊺}{\mathbf{A}}^{-1}\mathbf{u}}\right)(\mathbf{A}+\mathbf{u}{\mathbf{v}}^{⊺})=\mathbf{I}+{\mathbf{A}}^{-1}\mathbf{u}{\mathbf{v}}^{⊺}-\frac{{\mathbf{A}}^{-1}\mathbf{u}{\mathbf{v}}^{⊺}{\mathbf{A}}^{-1}(\mathbf{A}+\mathbf{u}{\mathbf{v}}^{⊺})}{1+{\mathbf{v}}^{⊺}{\mathbf{A}}^{-1}\mathbf{u}}\text{(1)}$

Since ${\mathbf{v}}^{⊺}{\mathbf{A}}^{-1}\mathbf{u}$ is a scalar, The numerator of the last term can be expressed as ${\mathbf{A}}^{-1}\mathbf{u}{\mathbf{v}}^{⊺}{\mathbf{A}}^{-1}(\mathbf{A}+\mathbf{u}{\mathbf{v}}^{⊺})={\mathbf{A}}^{-1}\mathbf{u}{\mathbf{v}}^{⊺}+({\mathbf{v}}^{⊺}{\mathbf{A}}^{-1}\mathbf{u}){\mathbf{A}}^{-1}\mathbf{u}{\mathbf{v}}^{⊺}=(1+{\mathbf{v}}^{⊺}{\mathbf{A}}^{-1}\mathbf{u}){\mathbf{A}}^{-1}\mathbf{u}{\mathbf{v}}^{⊺}$

So, $\text{(1)}=\mathbf{I}+{\mathbf{A}}^{-1}\mathbf{u}{\mathbf{v}}^{⊺}-\frac{(1+{\mathbf{v}}^{⊺}{\mathbf{A}}^{-1}\mathbf{u}){\mathbf{A}}^{-1}\mathbf{u}{\mathbf{v}}^{⊺}}{1+{\mathbf{v}}^{⊺}{\mathbf{A}}^{-1}\mathbf{u}}=\text{(1)}=\mathbf{I}+{\mathbf{A}}^{-1}\mathbf{u}{\mathbf{v}}^{⊺}-{\mathbf{A}}^{-1}\mathbf{u}{\mathbf{v}}^{⊺}=\mathbf{I}$ $\therefore (\mathbf{A}+\mathbf{u}{\mathbf{v}}^{⊺}{)}^{-1}={\mathbf{A}}^{-1}-\frac{{\mathbf{A}}^{-1}\mathbf{u}{\mathbf{v}}^{⊺}{\mathbf{A}}^{-1}}{1+{\mathbf{v}}^{⊺}{\mathbf{A}}^{-1}\mathbf{u}}$

Examples

Updating Fitted Least Square Estimator

Sherman–Morrison formula can be used for updating fitted Least Square estimator

Let $\hat{\mathbf{x}}=({\mathbf{A}}^{⊺}\mathbf{A}{)}^{-1}{\mathbf{A}}^{⊺}\mathbf{b}$ be the least square estimator of $\mathbf{Ax}=\mathbf{b}$ and the matrices with a new data be ${\mathbf{A}}_a=\left[\begin{array}{c}\mathbf{A}\\ {\mathbf{a}}^{⊺}\end{array}\right]$ and ${\mathbf{b}}_a=\left[\begin{array}{c}\mathbf{b}\\ b\end{array}\right]$ Then, ${\hat{\mathbf{x}}}_{\text{new}}=({\mathbf{A}}_a^{⊺}{\mathbf{A}}_a{)}^{-1}{\mathbf{A}}_a^{⊺}{\mathbf{b}}_a={\left(\left[\begin{array}{cc}{\mathbf{A}}^{⊺}& \mathbf{a}\end{array}\right]\left[\begin{array}{c}\mathbf{A}\\ {\mathbf{a}}^{⊺}\end{array}\right]\right)}^{-1}\left[\begin{array}{cc}{\mathbf{A}}^{⊺}& \mathbf{a}\end{array}\right]\left[\begin{array}{c}\mathbf{b}\\ b\end{array}\right]=({\mathbf{A}}^{⊺}\mathbf{A}+\mathbf{a}{\mathbf{a}}^{⊺}{)}^{-1}({\mathbf{A}}^{⊺}\mathbf{b}+b\mathbf{a})$

Let $\mathbf{P}:=({\mathbf{A}}^{⊺}\mathbf{A}{)}^{-1}$ for convenience Then, ${\mathbf{P}}_a:=({\mathbf{A}}^{⊺}\mathbf{A}+\mathbf{a}{\mathbf{a}}^{⊺}{)}^{-1}=\mathbf{P}-\frac{\mathbf{Pa}{\mathbf{a}}^{⊺}\mathbf{P}}{1+{\mathbf{a}}^{⊺}\mathbf{Pa}}=({\mathbf{A}}^{⊺}\mathbf{A}{)}^{-1}-\frac{({\mathbf{A}}^{⊺}\mathbf{A}{)}^{-1}\mathbf{a}{\mathbf{a}}^{⊺}({\mathbf{A}}^{⊺}\mathbf{A}{)}^{-1}}{1+{\mathbf{a}}^{⊺}({\mathbf{A}}^{⊺}\mathbf{A}{)}^{-1}\mathbf{a}}$ by Sherman-Morrison formula

So, ${\hat{\mathbf{x}}}_{\text{new}}=({\mathbf{A}}^{⊺}\mathbf{A}+\mathbf{a}{\mathbf{a}}^{⊺}{)}^{-1}({\mathbf{A}}^{⊺}\mathbf{b}+b\mathbf{a})=({\mathbf{A}}^{⊺}\mathbf{A}{)}^{-1}{\mathbf{A}}^{⊺}\mathbf{b}-\frac{\mathbf{Pa}{\mathbf{a}}^{⊺}\mathbf{P}}{1+{\mathbf{a}}^{⊺}\mathbf{Pa}}{\mathbf{A}}^{⊺}\mathbf{b}+b{\mathbf{P}}_a\mathbf{a}=\hat{\mathbf{x}}-\frac{\mathbf{Pa}}{1+{\mathbf{a}}^{⊺}\mathbf{Pa}}{\mathbf{a}}^{⊺}\hat{\mathbf{x}}+b{\mathbf{P}}_a\mathbf{a}$ where ${\mathbf{P}}_a\mathbf{a}=\mathbf{Pa}-\frac{\mathbf{Pa}{\mathbf{a}}^{⊺}\mathbf{Pa}}{1+{\mathbf{a}}^{⊺}\mathbf{Pa}}=\frac{\mathbf{Pa}+\mathbf{Pa}{\mathbf{a}}^{⊺}\mathbf{Pa}-\mathbf{Pa}{\mathbf{a}}^{⊺}\mathbf{Pa}}{1+{\mathbf{a}}^{⊺}\mathbf{Pa}}=\frac{\mathbf{Pa}}{1+{\mathbf{a}}^{⊺}\mathbf{Pa}}$ by expansion $\therefore {\hat{\mathbf{x}}}_{\text{new}}=\hat{\mathbf{x}}-{\mathbf{P}}_a\mathbf{a}{\mathbf{a}}^{⊺}\hat{\mathbf{x}}+b{\mathbf{P}}_a\mathbf{a}=\hat{\mathbf{x}}+{\mathbf{P}}_a\mathbf{a}(b-{\mathbf{a}}^{⊺}\hat{\mathbf{x}})$

So, ${\hat{\mathbf{x}}}_{\text{new}}$ can be obtained without additional inverse matrix calculation.

Facts

Sherman–Morrison formula is a special case of the Woodbury Formula

Link to original

Matrix Inversion Lemma

Definition

$(\mathbf{A}+\mathbf{UCV}{)}^{-1}={\mathbf{A}}^{-1}-{\mathbf{A}}^{-1}\mathbf{U}({\mathbf{C}}^{-1}+\mathbf{V}{\mathbf{A}}^{-1}\mathbf{U}{)}^{-1}\mathbf{V}{\mathbf{A}}^{-1}$ where the size of matrices are $\mathbf{A}$ is $n\times n$, $\mathbf{C}$ is $k\times k$, and $\mathbf{V}$ is $k\times n$ and $\mathbf{A},\mathbf{C},({\mathbf{C}}^{-1}+\mathbf{V}{\mathbf{A}}^{-1}\mathbf{U})$ should be invertible.

The inverse of a rank-k correction of some matrix can be computed by doing a rank-k correction to the inverse of the original matrix

Proof

Start by the matrix $\left[\begin{array}{cc}\mathbf{A}& \mathbf{U}\\ \mathbf{V}& \mathbf{C}\end{array}\right]$

The $LD\mathbf{U}$ decomposition of the original matrix become $\left[\begin{array}{cc}\mathbf{A}& \mathbf{U}\\ \mathbf{V}& \mathbf{C}\end{array}\right]=\left[\begin{array}{cc}I& 0\\ \mathbf{V}{\mathbf{A}}^{-1}& I\end{array}\right]\left[\begin{array}{cc}\mathbf{A}& 0\\ 0& \mathbf{C}-\mathbf{V}{\mathbf{A}}^{-1}\mathbf{U}\end{array}\right]\left[\begin{array}{cc}I& {\mathbf{A}}^{-1}\mathbf{U}\\ 0& I\end{array}\right]$ Inverting both sides gives^[Diagonalizable Matrix] $\begin{array}{rl}{\left[\begin{array}{cc}\mathbf{A}& \mathbf{U}\\ \mathbf{V}& \mathbf{C}\end{array}\right]}^{-1}& ={\left[\begin{array}{cc}I& {\mathbf{A}}^{-1}\mathbf{U}\\ 0& I\end{array}\right]}^{-1}{\left[\begin{array}{cc}\mathbf{A}& 0\\ 0& \mathbf{C}-\mathbf{V}{\mathbf{A}}^{-1}\mathbf{U}\end{array}\right]}^{-1}{\left[\begin{array}{cc}I& 0\\ \mathbf{V}{\mathbf{A}}^{-1}& I\end{array}\right]}^{-1}\\ & =\left[\begin{array}{cc}I& -{\mathbf{A}}^{-1}\mathbf{U}\\ 0& I\end{array}\right]\left[\begin{array}{cc}{\mathbf{A}}^{-1}& 0\\ 0& {\left(\mathbf{C}-\mathbf{V}{\mathbf{A}}^{-1}\mathbf{U}\right)}^{-1}\end{array}\right]\left[\begin{array}{cc}I& 0\\ -\mathbf{V}{\mathbf{A}}^{-1}& I\end{array}\right]\\ & =\left[\begin{array}{cc}{\mathbf{A}}^{-1}+{\mathbf{A}}^{-1}\mathbf{U}{\left(\mathbf{C}-\mathbf{V}{\mathbf{A}}^{-1}\mathbf{U}\right)}^{-1}\mathbf{V}{\mathbf{A}}^{-1}& -{\mathbf{A}}^{-1}\mathbf{U}{\left(\mathbf{C}-\mathbf{V}{\mathbf{A}}^{-1}\mathbf{U}\right)}^{-1}\\ -{\left(\mathbf{C}-\mathbf{V}{\mathbf{A}}^{-1}\mathbf{U}\right)}^{-1}\mathbf{V}{\mathbf{A}}^{-1}& {\left(\mathbf{C}-\mathbf{V}{\mathbf{A}}^{-1}\mathbf{U}\right)}^{-1}\end{array}\right](1)\end{array}$

The $\mathbf{U}DL$ decomposition of the original matrix become $\left[\begin{array}{cc}\mathbf{A}& \mathbf{U}\\ \mathbf{V}& \mathbf{C}\end{array}\right]=\left[\begin{array}{cc}I& \mathbf{U}{\mathbf{C}}^{-1}\\ 0& I\end{array}\right]\left[\begin{array}{cc}\mathbf{A}-\mathbf{U}{\mathbf{C}}^{-1}\mathbf{V}& 0\\ 0& \mathbf{C}\end{array}\right]\left[\begin{array}{cc}I& 0\\ {\mathbf{C}}^{-1}\mathbf{V}& I\end{array}\right]$ Again inverting both sides, $\begin{array}{rl}{\left[\begin{array}{cc}\mathbf{A}& \mathbf{U}\\ \mathbf{V}& \mathbf{C}\end{array}\right]}^{-1}& ={\left[\begin{array}{cc}I& 0\\ {\mathbf{C}}^{-1}\mathbf{V}& I\end{array}\right]}^{-1}{\left[\begin{array}{cc}\mathbf{A}-\mathbf{U}{\mathbf{C}}^{-1}\mathbf{V}& 0\\ 0& \mathbf{C}\end{array}\right]}^{-1}{\left[\begin{array}{cc}I& \mathbf{U}{\mathbf{C}}^{-1}\\ 0& I\end{array}\right]}^{-1}\\ & =\left[\begin{array}{cc}I& 0\\ -{\mathbf{C}}^{-1}\mathbf{V}& I\end{array}\right]\left[\begin{array}{cc}{\left(\mathbf{A}-\mathbf{U}{\mathbf{C}}^{-1}\mathbf{V}\right)}^{-1}& 0\\ 0& {\mathbf{C}}^{-1}\end{array}\right]\left[\begin{array}{cc}I& -\mathbf{U}{\mathbf{C}}^{-1}\\ 0& I\end{array}\right]\\ & =\left[\begin{array}{cc}{\left(\mathbf{A}-\mathbf{U}{\mathbf{C}}^{-1}\mathbf{V}\right)}^{-1}& -{\left(\mathbf{A}-\mathbf{U}{\mathbf{C}}^{-1}\mathbf{V}\right)}^{-1}\mathbf{U}{\mathbf{C}}^{-1}\\ -{\mathbf{C}}^{-1}\mathbf{V}{\left(\mathbf{A}-\mathbf{U}{\mathbf{C}}^{-1}\mathbf{V}\right)}^{-1}& {\mathbf{C}}^{-1}+{\mathbf{C}}^{-1}\mathbf{V}{\left(\mathbf{A}-\mathbf{U}{\mathbf{C}}^{-1}\mathbf{V}\right)}^{-1}\mathbf{U}{\mathbf{C}}^{-1}\end{array}\right](2)\end{array}$

The first-row first-column entry of RHS of (1) and (2) above gives the Woodbury formula ${\left(\mathbf{A}-\mathbf{U}{\mathbf{C}}^{-1}\mathbf{V}\right)}^{-1}={\mathbf{A}}^{-1}+{\mathbf{A}}^{-1}\mathbf{U}{\left(\mathbf{C}-\mathbf{V}{\mathbf{A}}^{-1}\mathbf{U}\right)}^{-1}\mathbf{V}{\mathbf{A}}^{-1}$

Link to original

Moore-Penrose Inverse

Definition

For a $p\times q$ matrix $A$, the Moore-Penrose inverse of $A$ is a $q\times p$ matrix $A^{+}$ is satisfying the following conditions

• $A{A}^{+}A=A$
• $A^{+}A{A}^{+}=A^{+}$
• $(A{A}^{+}{)}^{†}=A{A}^{+}$¹
• $(A^{+}A{)}^{†}=A^{+}A$¹

Facts

The pseudoinverse is defined and unique for all matrices whose entries are real and complex numbers.

If the matrix $A$ is a square matrix, then $A^{+}$ is also a square matrix and $A^{+}=A^{-1}$

Footnotes

1. Hermitian Matrix ↩ ↩²

Link to original

Partitioned Matrix

Block Matrix

Definition

A matrix that is interpreted as having been broken into sections called blocks or sub-matrices

Operations

Addition, Subtraction

$\left[\begin{array}{ccc}{\mathbf{A}}_{11}& \dots & {\mathbf{A}}_{1n}\\ ⋮& & ⋮\\ {\mathbf{A}}_{m1}& \dots & {\mathbf{A}}_{mn}\end{array}\right]\pm \left[\begin{array}{ccc}{\mathbf{B}}_{11}& \dots & {\mathbf{B}}_{1n}\\ ⋮& & ⋮\\ {\mathbf{B}}_{m1}& \dots & {\mathbf{B}}_{mn}\end{array}\right]=\left[\begin{array}{ccc}{\mathbf{A}}_{11}\pm {\mathbf{B}}_{11}& \dots & {\mathbf{A}}_{1n}\pm {\mathbf{B}}_{1n}\\ ⋮& & ⋮\\ {\mathbf{A}}_{m1}\pm {\mathbf{B}}_{m1}& \dots & {\mathbf{A}}_{mn}\pm {\mathbf{B}}_{mn}\end{array}\right]$

Scalar Multiplication

$c\left[\begin{array}{ccc}{\mathbf{A}}_{11}& \dots & {\mathbf{A}}_{1n}\\ ⋮& & ⋮\\ {\mathbf{A}}_{m1}& \dots & {\mathbf{A}}_{mn}\end{array}\right]=\left[\begin{array}{ccc}c{\mathbf{A}}_{11}& \dots & c{\mathbf{A}}_{1n}\\ ⋮& & ⋮\\ c{\mathbf{A}}_{m1}& \dots & c{\mathbf{A}}_{mn}\end{array}\right]$

Matrix Multiplication

$\left[\begin{array}{ccc}{\mathbf{B}}_{11}& \dots & {\mathbf{B}}_{1n}\\ ⋮& & ⋮\\ {\mathbf{B}}_{k1}& \dots & {\mathbf{B}}_{kn}\end{array}\right]\left[\begin{array}{ccc}{\mathbf{A}}_{11}& \dots & {\mathbf{A}}_{1n}\\ ⋮& & ⋮\\ {\mathbf{A}}_{m1}& \dots & {\mathbf{A}}_{mn}\end{array}\right]=\left[\begin{array}{ccc}({\mathbf{B}}_{11}{\mathbf{A}}_{11}+\cdots +{\mathbf{B}}_{1m}{\mathbf{A}}_{m1})& \dots & ({\mathbf{B}}_{11}{\mathbf{A}}_{1n}+\cdots +{\mathbf{B}}_{1m}{\mathbf{A}}_{mn})\\ ⋮& & ⋮\\ ({\mathbf{B}}_{k1}{\mathbf{A}}_{11}+\cdots +{\mathbf{B}}_{km}{\mathbf{A}}_{m1})& \dots & ({\mathbf{B}}_{k1}{\mathbf{A}}_{1n}+\cdots +{\mathbf{B}}_{km}{\mathbf{A}}_{mn})\end{array}\right]$

Determinant

Let $D$ or $A$ be invertible matrices $\left|\begin{array}{cc}A& B\\ C& D\end{array}\right|=|D|\cdot |A-B{D}^{-1}C|=|A|\cdot |D-C{A}^{-1}B|$

Link to original

Eigenvalues and Eigenvectors

Eigendecomposition

Definition

$\mathbf{Av}=\lambda \mathbf{v}$ where $\mathbf{A}$ is a $n\times n$ matrix and $\mathbf{v}\ne 0$

If $\mathbf{Av}$ is a scalar multiple of non-zero vector $\mathbf{v}$, then $\lambda$ is the eigenvalue and $\mathbf{v}$ is the eigenvector.

Characteristic Polynomial

$|\mathbf{A}-\lambda \mathbf{I}|=0$ The values ${\lambda }_i$ satisfying the characteristic polynomial, are the eigenvalues of the matrix $\mathbf{A}$

Eigenspace

$E=\{\mathbf{v}:(\mathbf{A}-\lambda \mathbf{I})\mathbf{v}=0\}$

The set of all eigenvectors of $A$ corresponding to the same eigenvalue, together with the zero vector.

The Kernel of the matrix $(\mathbf{A}-\lambda \mathbf{I})$

Eigenvector: non-zero vector in the eigenspace

Algebraic Multiplicity

${\mu }_A({\lambda }_i)$

Let ${\lambda }_i$ be an eigenvalue of an $n\times n$ matrix $A$. The algebraic multiplicity ${\mu }_A({\lambda }_i)$ of the eigenvalue is its multiplicity as a root of a Characteristic Polynomial, that is, the largest k such that $(\lambda -{\lambda }_i{)}^k$

Geometric Multiplicity

${\gamma }_A({\lambda }_i)$ Let ${\lambda }_i$ be an eigenvalue of an $n\times n$ matrix $A$. The geometric multiplicity ${\gamma }_A({\lambda }_i)$ of the eigenvalue is the dimension of the Eigenspace associated with the eigenvalue.

Computation

1. Find the solution^[eigenvalues] of the Characteristic Polynomial.
2. Find the solution^[eigenvectors] of the Under-Constrained System $(\mathbf{A}-{\lambda }_i\mathbf{I}){\mathbf{v}}_i=0$ using the found eigenvalue.

Facts

There exists at least one eigenvector corresponding to the eigenvalue $\lambda$

Eigenvectors corresponding to different eigenvalues are always linearly independent.

When $\mathbf{A}$ is a normal or real Symmetric Matrix, the eigendecomposition is called Spectral Decomposition

$\mathrm{tr}(\mathbf{A})={\sum }_{i=1}^n{\lambda }_i$ The Trace of the matrix is equal to the sum of the eigenvalues of the matrix.

Proof Since the matrix $\mathbf{A}-\lambda \mathbf{I}$ only has $\lambda$ term on diagonal, and the calculation of cofactor deletes a row and a column, the coefficient of ${\lambda }^{n-1}$ of $\text{det}(\mathbf{A}-\lambda \mathbf{I})$ is always $-(a_{11}+a_{22}+\cdots +a_{nn})$. Also, since ${\lambda }_i$ are the solution of the Characteristic Polynomial, the expression is factorized as $\text{det}(\mathbf{A}-\lambda \mathbf{I})=(\lambda -{\lambda }_1)(\lambda -{\lambda }_2)\dots (\lambda -{\lambda }_n)$ and the coefficient of ${\lambda }^{n-1}$ become a $-({\lambda }_1+{\lambda }_2+\cdots +{\lambda }_n)$ Therefore, $-(a_{11}+a_{22}+\cdots +a_{nn})=-({\lambda }_1+{\lambda }_2+\cdots +{\lambda }_n)$ and $\text{Trace}(\mathbf{A})={\sum }_{i=1}^n{\lambda }_i$.

$|\mathbf{A}|={\prod }_{i=1}^n{\lambda }_i$ The Determinant of the matrix is equal to the product of the eigenvalues of the matrix.

Not all matrices have $n$ linearly independent eigenvectors.

When $\mathbf{Av}=\lambda \mathbf{v}$ holds,

• the eigenvalues of ${\mathbf{A}}^{-1}$ are $\frac{1}{\lambda }$ and the eigenvectors of the matrix ${\mathbf{A}}^{-1}$ are the same as $\mathbf{A}$.
• the eigenvalues of $A^k$ is ${\lambda }^k$
• the eigenvalues of $c\mathbf{A}$ is $c\lambda$
• the eigenvalues of $\mathbf{A}+c\mathbf{I}$ is $\lambda +c$
• the eigenvalues of $(\mathbf{A}+c\mathbf{I}{)}^{-1}$ is $1/(\lambda +c)$

$1\le {\gamma }_A({\lambda }_i)\le {\mu }_A({\lambda }_i)\le n$

An eigenvalue’s Geometric Multiplicity cannot exceed its Algebraic Multiplicity

$\exists P\text{ s.t. }A=PD{P}^{-1}\iff \forall {\lambda }_i:{\gamma }_A({\lambda }_i)={\mu }_A({\lambda }_i)$

the matrix is diagonalizable $\iff$ the Geometric Multiplicity is equal to the Algebraic Multiplicity for all eigenvalues

Let $A$ be a symmetric matrix. Then, $A$ has $r$ eigenvalues equal to $1$ and the rest zero $\iff A^2=A,\mathrm{rank}(A)=r$.

Link to original

The non-zero eigenvalues of $AB$ are the same as those of $BA$.

Link to original

Quadratic Forms and Positive Definite Matrix

Quadratic Form

Definition

$q(\mathbf{x})={\mathbf{x}}^{⊺}\mathbf{Ax}$ where $A$ is a Symmetric Matrix

A mapping $Q:V\to K$ where $V$ is a Module on Commutative Ring $K$ that has the following properties. $\forall k,l\in K,\forall u,v,w\in V$

• $Q(kv)=k^{2}Q(v)$
• $Q(u+v+w)=Q(u+v)+Q(v+w)+Q(u+w)-Q(u)-Q(v)-Q(w)$
• $Q(ku+lv)=k^{2}Q(u)+l^{2}Q(v)+klQ(u+v)-klQ(u)-klQ(v)$

Matrix Expressions

$a_1{x}_1^2+a_2{x}_2^2+2a_3{x}_1{x}_2\iff \left[\begin{array}{cc}{x}_1& x_2\end{array}\right]\left[\begin{array}{cc}{a}_1& a_3\\ a_3& a_2\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]$

$a_1{x}_1^2+a_2{x}_2^2+a_3{x}_3^2+2a_4{x}_1{x}_2+2a_5{x}_1{x}_3+2a_6{x}_2{x}_3\iff \left[\begin{array}{ccc}{x}_1& x_2& x_3\end{array}\right]\left[\begin{array}{ccc}{a}_1& a_4& a_5\\ a_4& a_2& a_6\\ a_5& a_6& a_3\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]$

Facts

Let $\mathbf{x}$ be a Random Vector and $A$ be a symmetric matrix of constants. If $E(\mathbf{x})=\mathbf{\mu }$ and $\mathrm{Var}(\mathbf{x})=\Sigma$, then the expectation of the quadratic form $Q:={\mathbf{x}}^{⊺}A\mathbf{x}$ is $E(Q)={\mathbf{\mu }}^{⊺}A\mathbf{\mu }+\mathrm{tr}(A\Sigma )$

Let $\mathbf{x}=(X_1,\dots ,X_n{)}^{⊺}$ be a Random Vector and $A$ be a symmetric matrix of constants. If $E(\mathbf{x})=\mathbf{\theta }=({\theta }_1,\dots ,{\theta }_n{)}^{⊺}$ and $\mathrm{Var}(X_i)={\mu }_2$, $E[(X_i-{\theta }_i{)}^3]={\mu }_3$, and $E[(X_i-{\theta }_i{)}^4]={\mu }_4$, where $i=1,2,\dots ,n$, then the variance of the quadratic form ${\mathbf{x}}^{⊺}A\mathbf{x}$ is $\mathrm{Var}({\mathbf{x}}^{⊺}A\mathbf{x})=({\mu }_4-3{\mu }_2^2){\mathbf{a}}^{⊺}\mathbf{a}+2{\mu }_2^2\mathrm{tr}(A^2)+4{\mu }_2{\mathbf{\theta }}^{⊺}{A}^2\mathbf{\theta }+4{\mu }_3{\mathbf{\theta }}^{⊺}A\mathbf{a}$ where $\mathbf{a}$ is the column vector of diagonal elements of $A$.

If $X_i\sim N({\theta }_i,{\mu }_2),i=1,\dots ,n$ and $X_i$‘s are independent, then $\mathrm{Var}({\mathbf{x}}^{⊺}A\mathbf{x})=2{\mu }_2^2\mathrm{tr}(A^2)+4{\mu }_2{\mathbf{\theta }}^{⊺}{A}^2\mathbf{\theta }$ If $X_i\sim N(0,1),i=1,\dots ,n$ and $X_i$‘s are independent, then $\mathrm{Var}({\mathbf{x}}^{⊺}A\mathbf{x})=2\mathrm{tr}(A^2)$

Let ${\mathbf{X}}^{⊺}\sim N(0,{\sigma }^2{I}_n)$, $Q:={\mathbf{X}}^{⊺}A\mathbf{X}/{\sigma }^2$, where $A$ is a Symmetric Matrix and $\mathrm{rank}(A)=r\le n$, then the MGF of $Q$ is $M(t)={\prod }_{i=1}^r(1-2t{\lambda }_i{)}^{-1/2}=|I-2tA{|}^{-1/2}$ where ${\lambda }_i$‘s are non-zero eigenvalue of $A$

Let $\mathbf{X}\sim N_n(\mathbf{\mu },\Sigma )$, where $\Sigma$ is Positive-Definite Matrix, then $Q=(\mathbf{X}-\mathbf{\mu }{)}^{⊺}{\Sigma }^{-1}(\mathbf{X}-\mathbf{\mu })\sim {\chi }^2(n)$

Let $\mathbf{X}\sim N(0,{\sigma }^2{I}_n)$, $Q={\mathbf{X}}^{⊺}A\mathbf{X}/{\sigma }^2$, where $A$ is a Symmetric Matrix and $\mathrm{rank}(A)=r\le n$, then $Q\sim {\chi }^2(r)\iff A=A^k$ where $k\in \mathbb{N}$

Let $\mathbf{X}\sim N(0,{\sigma }^2{I}_n)$, $Q_1={\mathbf{X}}^{⊺}A\mathbf{X}/{\sigma }^2,Q_2={\mathbf{X}}^{⊺}B\mathbf{X}/{\sigma }^2$, where $A,B$ are symmetric matrices, then $Q_1,Q_2$ are independent if and only if $AB=O$

Let $Q=Q_1+Q_2+\cdots +Q_{k-1}+Q_k$, where $Q,Q_1,Q_2,\dots ,Q_k$ are quadratic forms in Random Sample from $N(0,{\sigma }^2)$ If $Q/{\sigma }^2\sim {\chi }^2(r),Q_1/{\sigma }^2\sim {\chi }^2(r_1),Q_2/{\sigma }^2\sim {\chi }^2(r_2),\dots ,Q_{k-1}/{\sigma }^2\sim {\chi }^2(r_{k-1})$ and $Q_k$ is non-negative, then

• $Q_1,Q_2,\dots ,Q_k$ are independent
• $Q_k/{\sigma }^2\sim {\chi }^2(r-r_1-r_2-\cdots -r_{k-1})$

Let $\mathbf{X}=(X_1,X_2,\dots ,X_n)\sim N(0,{\sigma }^2{I}_n)$, $\sum _{i=1}^n{X}_i^2=Q_1+Q_2+\cdots +Q_k$, where $Q_j={\mathbf{X}}^{⊺}{A}_j\mathbf{X}$, where $\mathrm{rank}(A_j)=r_j\le n$, then $\forall j=\{1,2,\dots ,k\},\frac{Q_j}{{\sigma }^2}\sim {\chi }^2(r_j)\iff {\sum }_{j=1}^k{r}_j=n$

${\mathbf{x}}^{⊺}A\mathbf{x}-2{\mathbf{x}}^{⊺}\mathbf{b}=(\mathbf{x}-A^{-1}\mathbf{b}{)}^{⊺}A(\mathbf{x}-A^{-1}\mathbf{b})-{\mathbf{b}}^{⊺}{A}^{-1}\mathbf{b}$

Link to original

Positive-Definite Matrix

Definition

$M\succ 0\iff \forall \mathbf{z}\ne 0,{\mathbf{z}}^{⊺}M\mathbf{z}>0$

Matrix $M$, in which ${\mathbf{z}}^{⊺}M\mathbf{z}$ is positive for every non-zero column vector $\mathbf{z}$ is a positive-definite matrix

Facts

Let $M\succ 0$, then

• $A^{-1}\succ 0$
• $\mathrm{rank}(CA{C}^{⊺})=\mathrm{rank}(C)$ where $C$ is a $p\times n$ matrix.
• $\mathrm{rank}(C)=p\Rightarrow CM{C}^{⊺}\succ 0$
• The diagonal elements of $M$ are positive.
• For a Symmetric Matrix $B$, $\exists t,M-tB\succ 0$ for sufficiently small $|t|$
• $\forall \mathbf{b},\underset{\mathbf{h}:\mathbf{h}\ne 0}{\sup }\frac{({\mathbf{h}}^{⊺}\mathbf{b}{)}^2}{{\mathbf{h}}^{⊺}M\mathbf{h}}={\mathbf{b}}^{⊺}{A}^{-1}\mathbf{b}$
• $\exists M^{1/2}\succ 0\text{s.t.}(M^{1/2}{)}^2=M$

$M\succ 0\iff \exists R\text{s.t.}A=R{R}^{⊺}$ where $R$ is a non-singular matrix.

$M\succ 0\iff$ all the leading minor determinants of $M$ are positive.

$\mathrm{rank}(X)=p\Rightarrow X^{⊺}X\succ 0$

Link to original

Projection and Decomposition of Matrix

Projection Matrix

Definition

$P=A(A^{⊺}A{)}^{-1}{A}^{⊺}$

For some vector $\mathbf{b}$, $P\mathbf{b}$ is the projection of $\mathbf{b}$ onto $A$

Facts

The projection matrix $P$ is symmetric Idempotent Matrix

Consider a Symmetric Matrix $P$, then $P$ is idempotent with rank $r$ if and only if $r$ eigenvalues are $1$ and $n-r$ eigenvalues are $0$.

$\mathrm{tr}(P)=\mathrm{rank}(P)$

The projection matrix is Positive Semi-Definite Matrix

If $P_1$ and $P_2$ are projection matrices, and $P_1-P_2$ is Positive Semi-Definite Matrix, then

• $P_1{P}_2=P_2{P}_1=P_2$
• $P_1-P_2$ is a projection matrix.

Link to original

QR Decomposition

Definition

$\mathbf{A}=\mathbf{QR}$ Decomposition of matrix $\mathbf{A}$ into a product $\mathbf{A}=\mathbf{QR}$ of an orthonormal matrix $\mathbf{Q}$ and an upper triangular matrix $\mathbf{R}$.

Computation

Using the Gram Schmidt Orthonormalization

QR decomposition can be computed by Gram Schmidt Orthonormalization. Where $Q=[q_1,\dots ,q_n]$ is the matrix of orthonormal column vectors obtained by the orthonormalization and $\mathbf{R}=\left[\begin{array}{ccccc}{\mathbf{q}}_1^{⊺}{\mathbf{a}}_1& {\mathbf{q}}_1^{⊺}{\mathbf{a}}_2& {\mathbf{q}}_1^{⊺}{\mathbf{a}}_3& \cdots & {\mathbf{q}}_1^{⊺}{\mathbf{a}}_n\\ 0& {\mathbf{q}}_2^{⊺}{\mathbf{a}}_2& {\mathbf{q}}_2^{⊺}{\mathbf{a}}_3& \cdots & {\mathbf{q}}_2^{⊺}{\mathbf{a}}_n\\ 0& 0& {\mathbf{q}}_3^{⊺}{\mathbf{a}}_3& \cdots & {\mathbf{q}}_3^{⊺}{\mathbf{a}}_n\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& 0& 0& \cdots & {\mathbf{q}}_n^{⊺}{\mathbf{a}}_n\end{array}\right]$

Link to original

Cholesky Decomposition

Definition

$A=L{L}^{†}$

Decomposition of a Positive-Definite Matrix into the product of lower triangular matrix and its Conjugate Transpose.

Computation

Let $\mathbf{A}=\left[\begin{array}{ccc}{a}_{11}& a_{12}& a_{13}\\ a_{21}& a_{22}& a_{23}\\ a_{31}& a_{22}& a_{33}\end{array}\right]$ be Positive-Definite Matrix. Then, $\mathbf{A}=\mathbf{L}{\mathbf{L}}^{⊺}=\left[\begin{array}{ccc}{L}_{11}& 0& 0\\ L_{21}& L_{22}& 0\\ L_{31}& L_{32}& L_{33}\end{array}\right]\left[\begin{array}{ccc}{L}_{11}& L_{21}& L_{31}\\ 0& L_{22}& L_{32}\\ 0& 0& L_{33}\end{array}\right]=\left[\begin{array}{ccc}{L}_{11}^2& & \text{(symmetric)}\\ & & \\ L_{21}{L}_{11}& L_{21}^2+L_{22}^2& \\ & & \\ L_{31}{L}_{11}& L_{31}{L}_{21}+L_{32}{L}_{22}& L_{31}^2+L_{32}^2+L_{33}^2\end{array}\right]$ By setting the first-row first-column entry $L_{11}=\sqrt{a_{11}}$, can find other entries using substitution. $L_{21}=a_{21}/L_{11},L_{31}=a_{31}/L_{11},L_{22}=\sqrt{a_{22}-L_{21}^2},L_{32}=(a_{32}=L_{31}{L}_{21})/L_{22},L_{33}=\sqrt{a_{33}-L_{31}^2-L_{32}^2}$ By summarizing, $L_{ii}=\sqrt{a_{ii}-{\sum }_{k=1}^{i-1}{L}_{ik}^2}$, $L_{ij}=\frac{1}{L_{jj}}(a_{ij}-{\sum }_{k=1}^{j-1}{L}_{ik}{L}_{jk})$

Link to original

Spectral Theorem

Definition

$A=A^{†}\iff A=Q\mathbf{\Lambda }{Q}^{†}$ where $Q$ is a Unitary Matrix, and $\mathbf{\Lambda }=\mathrm{diag}({\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n)$

A matrix $A$ is a Hermitian Matrix if and only if $A$ is Unitary Diagonalizable Matrix.

Facts

Every Hermitian Matrix is diagonalizable, and has real-valued Eigenvalues and orthonormal eigenvector matrix.

For the Hermitian Matrix ${\mathbf{A}}^{†}=\mathbf{A}$, the every eigenvalue is real.

Proof For the eigendecomposition $\mathbf{Ax}=\lambda \mathbf{x}$, ${\mathbf{x}}^{†}\mathbf{Ax}={\mathbf{x}}^{†}\lambda \mathbf{x}=\lambda {\mathbf{x}}^{†}\mathbf{x}=\lambda ||\mathbf{x}||\Rightarrow \lambda =\frac{{\mathbf{x}}^{†}\mathbf{Ax}}{||\mathbf{x}||}$. Since $\mathbf{A}$ is hermitian, ${\mathbf{x}}^{†}\mathbf{Ax}\in \mathbb{R}$ and norm is always real. Therefore, every eigenvalue is real.

For the Hermitian Matrix ${\mathbf{A}}^{†}=\mathbf{A}$, the eigenvectors from different eigenvalues are orthogonal.

Proof Let the eigendecomposition $\mathbf{A}{\mathbf{x}}_1={\lambda }_1{\mathbf{x}}_1,\mathbf{A}{\mathbf{x}}_2={\lambda }_2{\mathbf{x}}_2$ where ${\lambda }_1\ne {\lambda }_2,{\mathbf{x}}_1\ne {\mathbf{x}}_2$. By the property of hermitian matrix, $(\mathbf{A}{\mathbf{x}}_1{)}^{†}{\mathbf{x}}_2={\mathbf{x}}_1^{†}{\mathbf{A}}^{†}{\mathbf{x}}_2={\mathbf{x}}_1^{†}{\lambda }_2{\mathbf{x}}_2={\lambda }_2{\mathbf{x}}_1^{†}{\mathbf{x}}_2$ and $(\mathbf{A}{\mathbf{x}}_1{)}^{†}{\mathbf{x}}_2=({\lambda }_1{\mathbf{x}}_1{)}^{†}{\mathbf{x}}_2={\bar{\lambda }}_1{\mathbf{x}}_1^{†}{\mathbf{x}}_2={\lambda }_1{\mathbf{x}}_1^{†}{\mathbf{x}}_2$ So, ${\lambda }_2{\mathbf{x}}_1^{†}{\mathbf{x}}_2={\lambda }_1{\mathbf{x}}_1^{†}{\mathbf{x}}_2\Rightarrow ({\lambda }_1-{\lambda }_2){\mathbf{x}}_1^{†}{\mathbf{x}}_2=0$. Since ${\lambda }_1\ne {\lambda }_2$, ${\mathbf{x}}_1^{†}{\mathbf{x}}_2=0$. Therefore, ${\mathbf{x}}_1^{†},{\mathbf{x}}_2$ are orthogonal.

Link to original

Singular Value Decomposition

Definition

${\mathbf{A}}_{n\times m}={\mathbf{U}}_{n\times n}{\mathbf{D}}_{n\times m}({\mathbf{V}}_{m\times m}{)}^{⊺}={\sum }_{i=1}^{\min (n,m)}{d}_i{U}_i{V}_i^{⊺}$ An arbitrary matrix ${\mathbf{A}}_{n\times m}$ can be decomposed to $\mathbf{UD}{\mathbf{V}}^{⊺}$.

For $n\ge m$ ${\mathbf{A}}_{n\times m}={\mathbf{U}}_{n\times m}{\mathbf{D}}_{m\times m}({\mathbf{V}}_{m\times m}{)}^{⊺}$ where ${\mathbf{U}}^{⊺}\mathbf{U}={\mathbf{I}}_m$ and ${\mathbf{V}}^{⊺}\mathbf{V}=\mathbf{V}{\mathbf{V}}^{⊺}={\mathbf{I}}_m$ and $\mathbf{D}$ is Diagonal Matrix

For $n\le m$ ${\mathbf{A}}_{n\times m}={\mathbf{U}}_{n\times n}{\mathbf{D}}_{n\times n}({\mathbf{V}}_{m\times n}{)}^{⊺}$ where ${\mathbf{U}}^{⊺}\mathbf{U}=\mathbf{U}{\mathbf{U}}^{⊺}={\mathbf{I}}_n$ and ${\mathbf{V}}^{⊺}\mathbf{V}={\mathbf{I}}_n$ and $\mathbf{D}$ is Diagonal Matrix

Calculation

For matrix ${\mathbf{A}}_{m\times n}=\mathbf{UD}{\mathbf{V}}^{⊺}$

${\mathbf{V}}_{n\times n}$ is the matrix of orthonormal eigenvectors of ${\mathbf{A}}^{⊺}\mathbf{A}$ ${\mathbf{U}}_{m\times m}$ is the matrix of orthonormal eigenvectors of $\mathbf{A}{\mathbf{A}}^{⊺}$ ${\mathbf{D}}_{m\times n}$ is the Diagonal Matrix made of the square roots of the non-zero eigenvalues of ${\mathbf{A}}^{⊺}\mathbf{A}$ and $\mathbf{A}{\mathbf{A}}^{⊺}$ sorted in descending order.

If the eigendecomposition is ${\mathbf{A}}^{⊺}\mathbf{Ax}=\lambda \mathbf{x}$, then the eigenvalues $\lambda \ge 0$ and the eigenvectors $\mathbf{x}\in \mathbb{C}({\mathbf{A}}^{⊺})$ are orthonormal by Spectral Theorem. If the $\mathrm{rank}(\mathbf{A})=r\le n$, then ${\lambda }_1⪈{\lambda }_2⪈\cdots \ge {\lambda }_r,{\lambda }_{r+1}=\dots {\lambda }_n=0$. Where ${\sigma }_i=\sqrt{{\lambda }_i}{}_{i=1,2,\dots ,r}$ are called the singular values.

Now, the Orthonormal Matrix $\mathbf{V}=[{\mathbf{V}}_1,{\mathbf{V}}_2]$ is calculated using the singular values. Where $V_1=[{\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_r]$ is the Orthonormal Matrix of eigenvectors corresponding to the non-zero eigenvalues and $V_2=[{\mathbf{v}}_{r+1},{\mathbf{v}}_{r+2},\dots ,{\mathbf{v}}_n]$ is the Orthonormal Matrix of eigenvectors corresponding to zero eigenvalues where each ${\mathbf{v}}_r+i\in \mathbf{N}({\mathbf{A}}^{⊺}\mathbf{A})=\mathbf{N}(\mathbf{A})$, and ${\mathbf{D}}_{m\times n}=\mathrm{diag}({\sigma }_1,{\sigma }_2,\dots ,{\sigma }_r,0,\dots ,0)$ is a rectangular Diagonal Matrix.

Since $\mathbf{V}$ is an orthonormal matrix and $\mathbf{D}$ is a Diagonal Matrix, $\mathbf{AV}=\mathbf{UD}\Rightarrow \mathbf{A}[{\mathbf{v}}_1,{\mathbf{v}}_2,\dots ,{\mathbf{v}}_n]=[{\mathbf{u}}_1,{\mathbf{u}}_2,\dots ,{\mathbf{u}}_m]\mathbf{D}\Rightarrow \mathbf{A}{\mathbf{v}}_i={\sigma }_i{\mathbf{u}}_i\Rightarrow {\mathbf{u}}_i=\frac{1}{{\sigma }_i}\mathbf{A}{\mathbf{v}}_i$. Now, the Orthonormal Matrix $\mathbf{U}=[{\mathbf{U}}_1,{\mathbf{U}}_2]$ is calculated using the linear system $\frac{1}{{\sigma }_i}\mathbf{A}{\mathbf{v}}_i$ and the null space of $\mathbf{A}$, $\mathbf{N}(\mathbf{A})$ Where ${\mathbf{U}}_1=[{\mathbf{u}}_1,{\mathbf{u}}_2,\dots ,{\mathbf{u}}_r]$ is the Orthonormal Matrix of the vectors ${\mathbf{u}}_{\{1,2,\dots ,r\}}\in \mathbf{C}(\mathbf{A})$ obtained from the system equation $\frac{1}{{\sigma }_i}\mathbf{A}{\mathbf{v}}_i$ And ${\mathbf{U}}_2=[{\mathbf{u}}_{r+1},{\mathbf{u}}_{r+2},\dots ,{\mathbf{u}}_m]$ is the Orthonormal Matrix of the vectors ${\mathbf{u}}_{\{r+1,r+2,\dots ,m\}}\in \mathbf{N}({\mathbf{A}}^{⊺})$. which is corresponding to zero eigenvalues

The Orthonormal Matrix $\mathbf{U}=[{\mathbf{u}}_1,{\mathbf{u}}_2,\dots ,{\mathbf{u}}_m]$ can also be formed by the eigenvectors of $\mathbf{A}{\mathbf{A}}^{⊺}$ similarly to calculating of $\mathbf{V}$.

Facts

$\mathbf{U},\mathbf{V}$ are the Unitary Matrix

Let $\mathbf{A}$ be a real symmetric Positive Semi-Definite Matrix Then, the Eigendecomposition(Spectral Decomposition) of $\mathbf{A}$ and the singular value decomposition of $\mathbf{A}$ are equal.

$\mathbf{A}=\mathbf{P\Lambda }{\mathbf{P}}^{⊺}=\mathbf{UD}{\mathbf{V}}^{⊺}$ where $\mathbf{P}=\mathbf{U}=\mathbf{V}$ and $\mathbf{\Lambda }=\mathbf{D}$ are non-negative and the shape of the every matrix is $n\times n$

Visualization

every matrix can be decomposed as a

• ${\mathbf{V}}^{⊺}$: rotation and reflection
• $\mathbf{D}$: scaling
• $\mathbf{U}$: rotation and reflection

Link to original

Miscellanea in Matrix

Centering Matrix

Definition

$C=I-\frac{1}{n}{J}_n$ where $J_n=1_n{1}^{⊺}$ is $n\times n$ matrix where all elements are $1$

Summing Vector

$1_n=(1,1,\dots ,1{)}^{⊺}$

Facts

$(n-1)s^2={\mathbf{x}}^{⊺}C\mathbf{x}$ where $s^2$ is a sample variance of $\mathbf{x}$

Link to original

Derivatives of Matrix

Definition

Differentiation by vector

$\frac{\partial }{\partial {\mathbf{x}}^{⊺}}:=\left[\frac{\partial }{\partial x_1},\frac{\partial }{\partial x_2},\dots ,\frac{\partial }{\partial x_n}\right]$ where $\mathbf{x}=[x_1,x_2,\dots ,x_n]$

Differentiation by Matrix

$\frac{\partial }{\partial X}:=\left[\begin{array}{ccc}\frac{\partial }{\partial x_{11}}& \dots & \frac{\partial }{\partial x_{1p}}\\ ⋮& \ddots & ⋮\\ \frac{\partial }{\partial x_{n1}}& \dots & \frac{\partial }{\partial x_{np}}\end{array}\right]$ where $X=\left[\begin{array}{ccc}{x}_{11}& \dots & x_{1p}\\ ⋮& \ddots & ⋮\\ x_{n1}& \dots & x_{np}\end{array}\right]$

Calculation

Let $f$ be a vector function, $\mathbf{x}$ be an $n$-dimensional vector, then $\frac{\partial f}{\partial {\mathbf{x}}^{⊺}}=\left[\frac{\partial f}{\partial x_1},\frac{\partial f}{\partial x_2},\dots ,\frac{\partial f}{\partial x_n}\right]$ By the definition of derivative, we hold $\mathbf{df}=f(\mathbf{x}+d\mathbf{x})-f(\mathbf{x})=\frac{\partial f}{\partial x_1}d{x}_1+\frac{\partial f}{\partial x_2}d{x}_2+\cdots +\frac{\partial f}{\partial x_n}d{x}_n=\frac{\partial f}{\partial {\mathbf{x}}^{⊺}}d\mathbf{x}$ where $d\mathbf{x}=[d{x}_1,d{x}_2{]}^{⊺}$

Examples

Let $\mathbf{x},\mathbf{y}$ be $n$-dimensional vectors, then $\frac{\partial }{\partial \mathbf{x}}({\mathbf{x}}^{⊺}\mathbf{y})=\frac{\partial }{\partial \mathbf{x}}({\mathbf{y}}^{⊺}\mathbf{x})=\mathbf{y}$

Let $\mathbf{x}$ be an $n$-dimensional vector and $A$ be an $n\times n$ matrix, then $\frac{\partial }{\partial \mathbf{x}}({\mathbf{x}}^{⊺}A)=A,\frac{\partial }{\partial \mathbf{x}}(A\mathbf{x})=A^{⊺}$

Let $\mathbf{x}$ be an $n$-dimensional vector and $A$ be an $n\times n$ Symmetric Matrix, then the derivative of quadratic form is $\frac{\partial }{\partial \mathbf{x}}({\mathbf{x}}^{⊺}A\mathbf{x})=A\mathbf{x}+A^{⊺}\mathbf{x}=2A\mathbf{x}$

Link to original

Hessian Matrix

Definition

$H_f=\left\{\frac{{\partial }^{2}f}{\partial x_i\partial x_j}\right\}=\left[\begin{array}{cccc}\frac{{\partial }^{2}f}{\partial x_1^2}& \frac{{\partial }^{2}f}{\partial x_1\partial x_2}& \dots & \frac{{\partial }^{2}f}{\partial x_1\partial x_n}\\ \frac{{\partial }^{2}f}{\partial x_2{x}_1}& \frac{{\partial }^{2}f}{\partial x_2^2}& \dots & \frac{{\partial }^{2}f}{\partial x_2\partial x_n}\\ ⋮& ⋮& \ddots & ⋮\\ \frac{{\partial }^{2}f}{\partial x_n\partial x_1}& \frac{{\partial }^{2}f}{\partial x_n\partial x_2}& \dots & \frac{{\partial }^{2}f}{\partial x_n^2}\end{array}\right]$

A square matrix of second-order partial derivative of a scalar-valued function

Link to original

Vectorization

Definition

Let $A=[{\mathbf{a}}_1,{\mathbf{a}}_2,\dots ,{\mathbf{a}}_n]$ be an $m\times n$ matrix, then $\mathrm{vec}(A)=[a_{11},a_{21},\dots ,a_{m1},a_{12},a_{22},\dots ,a_{m2},\dots ,a_{1n},a_{2n},\dots ,a_{mn}{]}^{⊺}$

A linear transformation which converts the matrix into a vector.

Facts

Let $A,B,C,Z$ be matrices, then

$\mathrm{vec}(ABC)=(C^{⊺}\otimes A)\mathrm{vec}(B)$ $\mathrm{tr}(AB)=\mathrm{vec}(A^{⊺}{)}^{⊺}\mathrm{vec}(B)$ $\mathrm{tr}(A{Z}^{⊺}BZC)=\mathrm{vec}(Z^{⊺}{)}^{⊺}(CA\otimes B^{⊺})\mathrm{vec}(Z)$

Link to original

Kronecker Product

Definition

Let $A$ be an $m\times n$ matrix and $B$ be a $p\times q$ matrix, then the Kronecker product $A\otimes B$ is the $pm\times qn$ block matrix $A\otimes B=\left[\begin{array}{ccc}{a}_{11}B& \cdots & a_{1n}B\\ ⋮& \ddots & ⋮\\ a_{m1}B& \cdots & a_{mn}B\end{array}\right]$

Facts

Let $A,B,X,Y$ be matrices, then

$(A\otimes B{)}^{⊺}=A^{⊺}\otimes B^{⊺}$ $(A\otimes B)(X\otimes Y)=AX\otimes BY$ $(A\otimes B{)}^{-1}=A^{-1}\otimes B^{-1}$, where $A,B$ are square matrices $\mathrm{rank}(A\otimes B)=\mathrm{rank}(A)\mathrm{rank}(B)$ $\mathrm{tr}(A\otimes B)=\mathrm{tr}(A)\mathrm{tr}(B)$ $|A_{p\times p}\otimes B_{m\times m}|=|A{|}^m|B{|}^p$ Eigenvalues of $A\otimes B$ is the product of the eigenvalue of $A$ and the eigenvalue of $B$

Link to original

Norms

Norm

Definition

$\Vert \cdot \Vert :V\to {\mathbb{R}}_0^{+}$ A real-valued function with the following properties

• Positive definiteness: $\forall \mathbf{v}\in V:\Vert \mathbf{v}\Vert =0\iff \mathbf{v}=0$
• Absolute Homogeneity: $\forall \mathbf{v}\in V,k\in K:\Vert k\mathbf{v}\Vert =|k|\Vert \mathbf{v}\Vert$
• Sub additivity or Triange inequality: $\forall \mathbf{v},\mathbf{w}\in V:\Vert \mathbf{v}+\mathbf{w}\Vert \le \Vert \mathbf{v}\Vert +\Vert \mathbf{w}\Vert$ where $K\in \{\mathbb{R},\mathbb{C}\}$ on a vector space $(V,+,\cdot ,K)$

Vector

Real

Let $\mathbf{x}\in {\mathbb{R}}^n$ be an $n$-dimensional vector, then the $L_p$ norm of the $\mathbf{x}$ is defined as $\Vert \mathbf{x}{\Vert }_p:={\left({\sum }_{i=1}^n|x_i{|}^p\right)}^{1/p}$

Complex

Let $\mathbf{x}\in {\mathbb{C}}^n$ be an $n$-dimensional complex vector, then the $L_1$ norm of the $\mathbf{x}$ is defined as $\Vert \mathbf{x}\Vert ={\mathbf{x}}^{†}\mathbf{x}=\sqrt{{\sum }_{i=1}^n{\bar{x}}_i{x}_i}$

Function

$\Vert f\Vert =\sqrt{⟨f,f⟩}=\sqrt{{\int }_a^{b}f(x{)}^{2}dx}$: norm of $f$

Facts

$\Vert \frac{f(x)}{\Vert f\Vert }\Vert =1$

a norm can be induced by a Inner product $d(v,w)=\Vert v-w\Vert$

Link to original

Schatten Norm

Definition

Let $A$ be an $m\times n$ matrix, then the Schatten norm of $A$ is defined as $||A|{|}_p={\left({\sum }_{i=1}^{\min \{m,n\}}{\sigma }_i^p\right)}^{1/p}$ where ${\sigma }_i$ is the $i$-th singularvalue of $A$

Facts

$p=1$: Nuclear Norm

$p=2$: Frobenius Norm $p=\infty$: Spectral Norm

Link to original

Frobenius Norm

Definition

Let $A$ be an $m\times n$ matrix, then the Frobenius norm of $A$ is defined as $||A|{|}_F={\left({\sum }_{i=1}^m{\sum }_{h=1}^n|a_{ij}{|}^2\right)}^{1/2}=\sqrt{\mathrm{tr}(A^{†}A)}$

Link to original

Matrix p-Norm

Definition

Let $A$ be an $m\times n$ matrix, then the matrix p-norm of $A$ is defined as $||A|{|}_p=\underset{\mathbf{x}\ne 0}{\sup }\frac{||A\mathbf{x}|{|}_p}{||x|{|}_p}=\underset{||\mathbf{x}|{|}_p=1}{\max }||A\mathbf{x}|{|}_p$

Facts

When $p=2$, the norm is a Spectral Norm.

Link to original

Spectral Norm

Definition

Let $A$ be an $m\times n$ matrix, then the matrix p-norm of $A$ is defined as $||A|{|}_2=\sqrt{{\lambda }_{\max }(A^{†}A)}={\sigma }_{\max }(A)$

Link to original

Nuclear Norm

Definition

Let $A$ be an $m\times n$ matrix, then the nuclear norm of $A$ is defined as $||A|{|}_{\ast }=\mathrm{tr}(\sqrt{A^{†}A)})={\sum }_{i=1}^{\min \{m,n\}}{\sigma }_i(A)$

Link to original

L-pq Norm

Definition

$L_{pq}$ norm is an entry-wise matrix norm. $||A|{|}_{p,q}={\left(\sum _{i=1}^n{\left(\sum _{j=1}^n|a_{ij}{|}^p\right)}^{q/p}\right)}^{1/q}$ where $p,q\ge 1$

Facts

When $p=q=1$, the norm is the sum of the absolute values of every entry and is called a matrix $L_1$ norm.

Link to original

Rayleigh-Ritz Theorem

Definition

Let $A$ be an $n\times n$ Hermitian Matrix with eigenvalues sorted in descending order ${\lambda }_1,\dots ,{\lambda }_p$, where $p\le n$, then $\underset{\mathbf{x}\ne 0}{\max }\frac{{\mathbf{x}}^{⊺}A\mathbf{x}}{{\mathbf{x}}^{⊺}\mathbf{x}}=\underset{||\mathbf{x}|{|}_2=1}{\max }{\mathbf{x}}^{⊺}A\mathbf{x}={\lambda }_1$ $\underset{\mathbf{x}\ne 0}{\min }\frac{{\mathbf{x}}^{⊺}A\mathbf{x}}{{\mathbf{x}}^{⊺}\mathbf{x}}=\underset{||\mathbf{x}|{|}_2=1}{\min }{\mathbf{x}}^{⊺}A\mathbf{x}={\lambda }_p$

Link to original