Matrix

Description:

• We write $A\in {\mathbb{R}}^{m\times n}$
  • m rows and n columns
• A collection of vectors in rows or columns
  • $A=[a_1{a}_2...a_n]$ or $A=\left[\begin{array}{c}{a}_1^T\\ a_2^T\\ ...\\ a_n^T\end{array}\right]$
• Always think of matrix as a transformation for vectors

Matrix Algebra:

• Transpose:
  • Exchange row to colume
  • $[A^T](i,j)=A(j,i)=A_{ji}$
    • every element at $ij$ becomes at $ji$
• Matrix Addition/Subtraction:
  • Must have the same size
  • Match element by element
  • Resulting to a new matrix of same size
• Multiplication:
  • Multiply with a scalar: $k\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)=\left(\begin{array}{cc}ka& kb\\ kc& kd\end{array}\right)$
  • Matrix-Vector product:
    • Between a $m\times n$ matrix and a $n$-vector $x$
    • Returns a vector, like a linear map
      • A vector transformed by the matrix
    • Denote by $Ax$, the $m$-vector with $i$-th component as $(Ax{)}_i={\sum }_{j=1}^n{A}_{ij}{x}_j,i=1,...m$
      • 
      • $y_1=A_{11}{x}_1+A_{12}{x}_2,$
      • $y_2=A_{21}{x}_1+A_{22}{x}_2,$
      • $y_3=A_{31}{x}_1+A_{32}{x}_2$
    • If the columns of matrix $A$ is given by vectors $a_i$ by columns, then $Ax$ can be intepreted as Linear Combination of the columns, $Ax=\sum _{i=1}^n{x}_i{a}_i$
      • 
      • Then we have $Ax=y=x_1\left(\begin{array}{c}{A}_{11}\\ A_{21}\\ A_{31}\end{array}\right)+x_2\left(\begin{array}{c}{A}_{12}\\ A_{22}\\ A_{32}\end{array}\right)$
      • Think of vectors within matrix as the transformation for the the input (vector)
  • Vector-Matrix product:
    • We first need to transpose vector $c\in {\mathbb{R}}^m$ to have $(c^{⊺}A{)}_j=\sum _{i=1}^m{A}_{ij}{z}_i,j=1,...n$
  • Matrix-Matrix product:
    • Defines for $A\in {\mathbb{R}}^{m\times n}$ and $B\in {\mathbb{R}}^{n\times p}$
    • Combine matrix A and matrix B in 1 matrix
    • $AB$ returns the $m\times p$ matrix with $i,j$ element given by $(AB{)}_{ij}=\sum _{k=1}^n{A}_{ik}{B}_{kj}$
      • column $i$ of A linear combine with row $j$ of B
    • Column-wise interpretation:
      • $AB=A\left(\begin{array}{ccc}{b}_1& \dots & b_p\end{array}\right)=\left(\begin{array}{ccc}A{b}_1& \dots & A{b}_p\end{array}\right)$
      • which is matrix-vector product
    • Row-wise interpretation:
      • $AB=\left(\begin{array}{c}{a}_1^{⊺}\\ ⋮\\ a_m^{⊺}\end{array}\right)B=\left(\begin{array}{c}{a}_1^{⊺}B\\ ⋮\\ a_m^{⊺}B\end{array}\right)$
      • which is vector-matrix product
    • Generally, $AB\ne BA$
  • $A^m{A}^n=A^n{A}^m=A^{m+n}$
  • $(AB{)}^T=B^T.A^T$
  • $(AB)CD=A(BC)D=AB(CD)$
• Division:
  • By Inverse

As Linear System of Equations

Some classes of matrices:

• Square Matrix
  • Identity Matrix
  • Diagonal Matrix
  • Triangle Matrix
  • Symmetric Matrix
  • Orthogonal Matrix
• Low-rank matrix:
  • Ranks are defined by the number of unique vectors in the matrix
  • Rank one: Dyad
• Zero matrix:
  • $0_{22}=\left(\begin{array}{cc}0& 0\\ 0& 0\end{array}\right)$
• Ones matrix

Matrix as linear map:

• Vector function
• A map $f:{\mathbb{R}}^n\to {\mathbb{R}}^m$ can be represented by a matrix $A\in {\mathbb{R}}^{m\times n}$, mapping input vectors $x\in {\mathbb{R}}^n$ to output a vector $y\in {\mathbb{R}}^m$
• $y=Ax$ where $A$ is a matrix $A\in {\mathbb{R}}^{m\times n}$
• Affine maps are linear functions with a constant vector:
  • $f(x)=Ax+b$ for some $A\in {\mathbb{R}}^{m\times n},b\in {\mathbb{R}}^m$

Matrix Range and Rank:

• For matrix $A\in R^{m\times n},A=\left[\begin{array}{cccc}{a}_1& a_2& ...& a_n\end{array}\right]$ which are vectors, 1 vector $a_i\in {\mathbb{R}}^m$ each
  • each $a_i$ is a column space
  • row space also exist for $A^{⊺}$
• Matrix transformation will result to a new space where the solution exist
  • range of a matrix is the space that the solution can exist in
• The range of $A$, $R(A)=\{Ax:x\in {\mathbb{R}}^n\}$
  • ex: $R(A)=\left[\begin{array}{cc}1& 4\\ 2& 5\\ 3& 6\end{array}\right].\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]=\left[\begin{array}{c}1x_1+4x_2\\ 2x_1+5x_2\\ 3x_1+6x_2\end{array}\right]=x_1\left[\begin{array}{c}1\\ 2\\ 3\end{array}\right]+x_2\left[\begin{array}{c}4\\ 5\\ 6\end{array}\right]$
  • now $x_1$ and $x_2$ forms a Linear Combination of vector
  • so $R(A)$ is a Subspace, span with basis $a_i$
• ie, $Ax\in R(A)$
• $rank(A)$, rank of $A$ is dimension of $R(A)$
  • rank represents the number of linear independent columns of $A$
    • so the matrix transformation output will have nb of dimension = $R(A)$
  • Full rank means all vectors columns are linear independent
  • $1\le \text{rank}(A)\le \min (m,n)$
    • as, for example:
      • span column space of $A=span(x_1\left[\begin{array}{c}1\\ 2\\ 3\end{array}\right]+x_2\left[\begin{array}{c}4\\ 5\\ 6\end{array}\right])=2$
      • span row space of $A$, column space of $A^{⊺}=span(x_1\left[\begin{array}{c}1\\ 4\end{array}\right]+x_2\left[\begin{array}{c}2\\ 5\end{array}\right]+x_3\left[\begin{array}{c}3\\ 6\end{array}\right])=2$
      • The dimension of the range is capped by the dimension number of vectors

Nullspace of matrix:

• Nullspace of matrix $A\in {\mathbb{R}}^{m.n}$ is a subspace
• The set of vectors in the input space that are mapped to zero, denoted by $\mathcal{N}(A)=\{x\in {\mathbb{R}}^n:Ax=0\}$
  • As transformed by matrix, some vectors output to origin
  • example: map a 2d plan in 3d to a point, the 2d space is the null space
• $\mathcal{R}(A^{⊺})$ and $\mathcal{N}(A)$ are mutually orthogonal subspace
  • $\forall x\in \mathcal{R}(A^{⊺}),y\in \mathcal{N}(A):x^{⊺}y=0$
  • as they dot product is 0

Trace:

• The trace of a space matrix $A\in {\mathbb{R}}^{n\times n}$ is the sum of its diagonal elements
  • $A=\sum _{i=1}^{n}A(i,i)$
• The trace is a linear function of the entries of the matrix
• $trace(A)=trace(A^{⊺})$ for any square matrix $A$
• $trace(AB)=trace(BA)$ for any matrices $A\in {\mathbb{R}}^{n\times m},B\in {\mathbb{R}}^{m\times n}$

Matrix determinant:

• Think of matrix as tranformation, image 2 vectors forms a plan, the determinant denotes the ratio of size after / size before
  • if the determinant is 0 for a plane, then the matrix transformation squish all the plane to a line, or a point
  • generally, if the matrix is 0, it squishing everything to lower dimension
  • if the determinant is negative, meaning the plane flipped around
• Of a Square Matrix
• $det(A)=\sum _{j=1}^n(-1{)}^{i+j}A(i,j).det{A}^{(i,j)}$
  • inductive formula (Laplace’s determinant expansion)
  • where $i$ is any row, choosen at will
  • $A^{(i,j)}$ denotes a $(n-1)\times (n-1)$ submatrix of $A$ obtained by eliminating row $i$ and column $j$ from $A$
• $A\in {\mathbb{R}}^{n,n}\text{ is singular }⟺det(A)=0⟺\mathcal{N}(A)\text{ is not equal to }\{0\}$
• For any square matrix $A,B\in {\mathbb{R}}^{n,n}$ and a scalar $\alpha$:
  • $det(A)=det{A}^{⊺}$
  • $det(AB)=det(BA)=det(A)det(B)$
  • $det(\alpha A)={\alpha }^n\det (A)$

Orthonormal matrix:

• $U\in {\mathbb{R}}^{n,n}$
• We have $U^{⊺}U=U{U}^{⊺}=I_n$
  • Identity Matrix
• Hence $1=det(I_n)=det(U^{⊺}U)=(detU{)}^2$
  • $\to det(U)=\pm 1$

Matrix inverse:

• If $A\in {\mathbb{R}}^{n,n}$ is non-singular, $det\ne 0$, then we have $A^{-1}$ as the unique $n\times n$ such that $A{A}^{-1}=A^{-1}A=I_n$
  • If $A,B$ are both square nonsingular, then $(AB{)}^{-1}=B^{-1}{A}^{-1}$
• If $A$ is square and nonsingular then:
  • $(A^{⊺}{)}^{-1}=(A^{-1}{)}^{⊺}$
  • $\det (A)=\det (A^{⊺})=\frac{1}{\det (A^{-1})}$
• For a generic matrix $A\in {\mathbb{R}}^{m,n}$, pseudoinverse is:
  • if $m\ge n$, then $A^{li}$ is a left inverse of $A$, if $A^{li}A=I_n$
  • if $n\ge m$, then $A^{ri}$ is a right inverse of $A$, if $A^{ri}A=I_m$
  • In general, a matrix $A^{pi}$ is a pseudoinverse of $A$, if $A{A}^{pi}A=A$

Matrix Norm

Similar matrix:

• Two matrices $A,B\in {\mathbb{R}}^{n,n}$ are said to be similar if there exist a nonsingular matrix $P\in {\mathbb{R}}^{n,n}$ such that $B=P^{-1}AP$
  • any $P$ with $det(P)\ne 0$ with 3 linear independent column vector works
• Similar matrices are related to different representation of the same linear map, under a change of basis in the underlying space.
• They have same set of Eigenvalues
• Matrix $B=P^{-1}AP$ represents the linear map $y=Ax$, in the new basis defined by the columns of $P$

Eigenvector

Complex Matrix

Matrix Decomposition:

• Orthogonal-triangular Decomposition
• Singular Value Decomposition

Matrix Completion