Linear Algebra

$A$ m x n where $m$ is the number of rows and $n$ the number of columns.

Definitions

$Ax=a_1{x}_1+...+a_n{x}_n$ where $a_i$ is the ith column of the matrix.

$AB=[A{b}_1,...,A{b}_n]$, just each column vector of B acting on A.

For an inverse to exist, $Ax=0$ needs to have a unique solution.

Independent vectors $v_1,...,v_n$ i.e. it doesn’t exist ${\lambda }_2,...,{\lambda }_n$ s.t. $v_1={\lambda }_2{v}_2+...+{\lambda }_n{v}_n$.

Independent vectors form a basis in ${\mathbb{R}}^n$. Every vector in the space is a unique combination of those basis vectors.

Here are particular bases for Rn among all the choices we could make: Standard basis = columns of the identity matrix General basis = columns of any invertible matrix Orthonormal basis = columns of any orthogonal matrix

If $A$ is invertible, then $A^{T}A$ is invertible (follows from invertible), symmetric (always), and positive definite (less clear, probably to do with eigenvalues/singular valuess.

Similar matrices

• Two similar matrices describe the same linear map i.e. their mapping are isomorphic and the isomorphism is the matrix $S$. $S$ also called a change of basis.
• Two square matrices $A,B$ are called similar if there is an invertible matrix $S$ s.t. $A=S^{-1}BS$.
• Property: Similar matrices have the same characteristic polynomial (i.e. same eigenvalues).
  • Proof: $P_A(\lambda )=det(A-\lambda I)=det(S^{-1}BS-\lambda I)=det(S^{-1}(B-\lambda I)S)$ (using multiplicative property of determinant) = $det(S^{-1})det(B-\lambda I)det(S)=det(I)det(B-\lambda I)=P_B(\lambda )$.

• Column and row space

Definition: The column space contains all the combinations of the columns

Useful decomposition if A is not full rank One can always decompose a matrix $A$ into column matrix and row matrix $A=CR$ where A is m x n, C is m x r, R is r x n.

For a 3x3 matrix with rank $r=2$, one can decompose into $A=CR$ where C is 3x2 (columns of C are a basis for the column space) and R is 2x3 (rows of R are a basis for the row space).

$R$ is the identity $I$ if $A$ is full-rank. Otherwise, it will be a block matrix $[I_R,D]$ where the columns of $D$ describe how to get the columns $r+1, …, n by using the previous columns.

Orthogonality of null-spaces and column spaces

• Remember that Ax=0 means that a dot product between x and every row of A is equal to zero.

Motivation for least squares

Suppose A is tall and thin (m > n). The n columns are likely to be independent. But if b is not in the column space, Ax = b has no solution. The least squares method minimizes $\Vert b-Ax{\Vert }^2$ by solving $A^{T}A\hat{x}=A^{T}b$ (i.e. project $Ax=b$ into row space ).

Orthogonal vectors

• $Q^{T}Q=\alpha I$ , columns are orthogonal, (dot product between columns)
• orthonormal, the columns are also unit vectors, $Q^{T}Q=I$.
• If $Q$ is square, then $Q{Q}^T=I$ also, and thus $Q^T=Q^{-1}$.
• $Q$ are rotation transforms. Indeed, $||Qx|{|}^2=||x|{|}^2$.
• For the eigenvalues of $Q$, $Qx=\lambda x$ ⇒ $||Qx|{|}^2=|\lambda {|}^2||x|{|}^2$ ⇒ $\lambda =\pm 1$
• For A full-rank, we can orthogonalize
  • $A=QR$. Then the columns of $Q$ are orthornormal. $R$ is upper-triangular (by Gram-Schmidt iterative construction).
    • 
  • Example for least squares:
    • $m>n$, $m$ equations $Ax=b$, $n$ unknowns, minimize $||b-Ax||=||e|{|}^2$.
    • Normal equations for the best $\hat{x}$: $A^{T}e=0$ or $A^{T}A\hat{x}=A^{T}b$. or $\hat{x}=(A^{T}A{)}^{-1}{A}^{T}b$.
    • If $A=QR$, then $R^T{Q}^{T}QR\hat{x}=R^T{Q}^{T}b$ which leads to $R\hat{x}=Q^{T}b$ (R is much easier to invert)

Eigenvalues and Eigenvectors

• An eigenvector $x$ with eigenvalue $\lambda$ of matrix $A$ (only for square matrices) is $Ax=\lambda x$
• To find the eigenvalues, we need to find the nullspace of $(A-\lambda I)$ i.e. $x$ s.t. $(A-\lambda I)x=0$
• There exists a nullspace iff $(A-\lambda I)$ is not invertible iff $det(A-\lambda I)=0$. This is the characteristic equation, and we solve for $\lambda$.
• Property: The eigenvalues of a triangular matrix are the entries on its main diagonal.

If not symmetric

• $A=X\Lambda X^{-1}$
• $A^2,A^3,...$ have the same eigenvectors as A. $A^n=X{\Lambda }^n{X}^{-1}$

Spectral theorem

• Let $S$ be a symmetric matrix

• Then $S=S^T$ has orthogonal eigenvectors $x^{T}y$ =0. (easy proof)

• Let $Q$ be the eigenvectors of $S$, then $SQ=\Lambda Q$ and thus, $S=Q\Lambda Q^{-1}=Q\Lambda Q^T$. (spectral theorem). This is a sum of a rank one matrices formed by $S=Q\Lambda Q^T={\lambda }_1{q}_1{q}_1^T+...+{\lambda }_r{q}_n{q}_n^T$

Singular values

• $A^{T}A$ is square, symmetric, nonnegative definite.
• With $S=A^{T}A$ (thus symmetric), this will lead to the singular values of A. SVD: $A=U\Sigma V^T$ with $U^{T}U=I$ and $V^{T}V=I$.
• We have $A^{T}A$ = $V{\Sigma }^T{U}^{T}U\Sigma V^T=V{\Sigma }^2{V}^T$.
• Indeed, the $v_i$ are eigenvectors of $A^{T}A$ and $A^{T}A$ is symmetric. $A^{T}A{v}_i={\lambda }_i={\sigma }_i^2{v}_i$. $V^{T}V=I$.
• We then have $AV=U\Sigma$ and thus $u_i=\frac{A{v}_i}{{\sigma }_i}$
• SVD
  • 

Trace

• $tr(A)$ is the divergence of the vector field created by $A$ ?
• divergence = rate of area change/area (of a local area around a point that evolves in a vector field).
• Usually, divergence is a quantity dependent on the position of the point within the vector field.
• But for the vector generated by matrix A, tr(A) is a constant.

Determinant

• Property 1. $det(I)=1$.

• Property 2. Exchange rows of $A$: reverse the sign of $det(A)$. Thus, for permutation matrices, $det(P)=\pm 1$.

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

• Property 3a. For $t\in \mathbb{R}$, $\left|\begin{array}{ccc}ta& tb& \\ c& d& \end{array}\right|=t\left|\begin{array}{ccc}a& b& \\ c& d& \end{array}\right|$

• Property 3b. For $a^{\prime }and{b}^{\prime }\in \mathbb{R}$, $\left|\begin{array}{ccc}a+a^{\prime }& b+b^{\prime }& \\ c& d& \end{array}\right|=\left|\begin{array}{ccc}a& b& \\ c& d& \end{array}\right|+\left|\begin{array}{ccc}{a}^{\prime }& b^{\prime }& \\ c& d& \end{array}\right|$

• $det$ is a linear operator for each row, while keeping other rows the same.

• Property 4. If there’s 2 equal rows → $det=0$ (test for invertibility). Proof: exchange the two equal rows. The determinant must change sign but the matrix is the same ⇒ $det=0$

PCA

• Given data matrix $X(n\times p)$ with $n$ datapoints and $p$ features, we can project $X$ into smaller dimensional space, which we will optimally linearly combine the features, according to least-squares, best low-rank approximation and Frobenius norm.
• $\hat{X}=XV$ where $V$ comes from the SVD decomposition $X=U\Sigma V^T$
• or the eigenvector decomposition of the covariance matrix (don’t forget to demean the data matrix) $X^{T}X=V\Lambda V^T$ because the covariance matrix is symmetric and positive-definite.

Big picture

• elimination $A=LU$
• orthogonalization $A=QR$
• eigenvalues $A=S\Delta S^{-1}$
• Singular values $A=U\Sigma V^T$