Linear Algebra Cheat Sheet (1)

0- Notations and convention

A variable/quantity/element can be scalar, vector, or a matrix; its type should be understood from the context if not explicitly declared.

0-1- A vector z\in \mathbb{F}^{n} is considered as a column vector, i.e. a single-column matrix. Therefore:

z\in \mathbb{F}^{n}\equiv z\in \mathbb{F}^{n\times 1}

A row vector is therefore defined as w^\text T\in \mathbb{F}^{1\times n}.

0-2- Dot product of column vectors:

\text{For }x,y\in \mathbb{R}^{n\times 1}, \ x\cdot y:=x^\text Ty

0-3- The ij-th element of a matrix A is denoted by A_{ij}. The i-th column and j-th row of the matrix are respectively denoted by A_{,i} and A_{j,} .

0-4- Columns and rows of a matrix are column and row vectors. A m\times n-matrix can then be represented as:

\begin{bmatrix} v_1& v_2& \dots & v_n\end{bmatrix}\ \text{ s.t } v_i=A_{,i}

or

\begin{bmatrix}u_1^\text T\\ u_2^\text T\\ \vdots\\ u_n^\text T\end{bmatrix}\ \text{ s.t } u_i^\text T=A_{i,}

1- Orthogonal matrix

a square matrix A\in \mathbb{R}^{n\times n} is said (definition) to be orthogonal iff A^{-1}=A^\text T; provided that A^{-1}, inverse of A exists. As a result, AA^{-1}=AA^\text T = I_n.

The following are equivalent for A:
a) A is orthogonal.
b) the column vectors of A are ortho-normal.
c) the row vectors of A are ortho-normal.
d) A is size preserving: \|Ax\|=\|x\|, \|.\| being the Euclidean norm, and x\in\ \mathbb{R}^{n\times 1}.
e) A is dot product preserving: Ax\cdot Ay=x\cdot y .

2- Some matrix multiplication identities

A\in \mathbb{F}^{m\times n},\ x\in \mathbb{F}^{n\times 1}\ \text{ then } Ax=\sum_{i=1}^n x_iA_{,i} A\in \mathbb{F}^{m\times n}\ , D\in \mathbb{F}^{n\times n}\ \text{ and diagonal }, B\in \mathbb{F}^{n\times k},\ \text{ s.t.}\\ \ \\ A=\begin{bmatrix} v_1& v_2& \dots & v_n\end{bmatrix}, \ B=\begin{bmatrix}u_1^\text T\\ \\ u_2^\text T\\ \vdots\\ u_n^\text T\end{bmatrix},\ D_{ij}= \begin{cases} \lambda_i &\text{, } i=j \\ 0 &\text{, } i\ne j \end{cases} \\ \ \\ \text{then }ADB=\sum_{i=1}^n \lambda_iv_i u_i^\text T

3- Change of basis

let \beta:=\{b_1,\dots,b_n\} and \beta':=\{b'_1,\dots,b'_n\} be two basis of \mathbb R^n. Then the following holds for the coordinates of a vector v\in\mathbb R^n with respect to the two bases:

[v]_{\beta’}=P_{\beta\to\beta’}[v]_{\beta}\quad\text{s.t} \\ \ \\ P_{\beta\to\beta’}=\begin{bmatrix} [b_1]_{\beta’}& [b_2]_{\beta’}& \dots & [b_n]_{\beta’}\end{bmatrix}

It can be proved that:

Rank of a Matrix

Let A\in \mathbb{R}^{m\times n} (the results also holds for \mathbb{C}^{m\times n}). Then, the column rank/row rank of A is defined as the dimension of the column/row space of A, i.e. the dimension of the vector space spanned by the columns/rows of A; this is then equivalent to the number of linearly independent columns/rows (column/rows vector) of A.

Theorem: column rank of A = row rank of A.

Definition: the rank of a matrix, rank(A), is the dimension of either the column or row space of A; simply the number of linearly independent columns or rows of A.

Definition: for a linear map f: \mathbb{R}^n\longrightarrow \mathbb{R}^m, the rank of the linear map is defined as the dimension of the image of f. This definition is equivalent to the definition of the matrix rank as every linear map f:\mathbb{R}^n\longrightarrow \mathbb{R}^m has a matrix A\in \mathbb{R}^{m\times n} by which it can be written as f(x)=Ax.

Proposition: \text{rank}(A)\le \min(m,n). This leads to these definitions: A matrix A is said to be full rank iff \text{rank}(A)= \min(m,n), i.e. the largest possible rank, and it is said to be rank deficient iff \text{rank}(A)\lt \min(m,n), i.e. not having full rank.

Properties of rank

For A\in \mathbb{R}^{m\times n}:

1- only a zero matrix has rank zero.

2- If B\in \mathbb{R}^{n\times k}, then \text{rank}(AB)\le \min( \text{rank}(A) , \text{rank}(B))

3- \text{rank}(A+B)\le \text{rank}(A)+ \text{rank}(B)

4- \text{rank}(A)=\text{rank}(A^{\text T})

5- \text{rank}(A)= \text{rank}(A^{\text T}) =\text{rank}(AA^{\text T})= \text{rank}(A^{\text T}A)

6- If v\in \mathbb{R}^{r\times 1}, then for V=vv^\text T \in \mathbb{R}^{r\times r}, \text{rank}(V)=1. In addition, for v_i \in \mathbb{R}^{r\times 1} , \text{rank}(S=\sum_{i=1}^{n} v_iv_i^\text T)\le n, i.e. S has at most rank n.

7- A square matrix C\in \mathbb{R}^{n\times n} can be decomposed as C=U\Gamma U^{-1} where \Gamma is a diagonal matrix containing the eigenvalues of C. Then, \text{rank}(C)=\text{rank}(\Gamma), i.e. the number of non-zero eigenvalues of C.

8- For a square matrix C\in \mathbb{R}^{n\times n} , then equivalently C is full rank, is invertible, has non-zero determinant, and has n non-zero eigenvalues.

Proofs

P6:

V=\begin{bmatrix}v_1\begin{bmatrix}v_1\\v_2\\ \vdots\\v_r \end{bmatrix}&v_2\begin{bmatrix}v_1\\v_2\\ \vdots\\v_r \end{bmatrix}&\dots &v_r\begin{bmatrix}v_1\\v_2\\ \vdots\\v_r \end{bmatrix}\end{bmatrix}

where v_i\in \mathbb{R} are coordinates of the vector v. This indicates that each column of V is a scalar multiple of any other columns of V; therefore, the column space is one dimensional. Hence, \text{rank}(V)=1.

For the second part, property 3 proves the statement.