03 - Matrices

Vandermonde Matrix

Let the pairs of data points be

$$\{(x_k,f_k){\}}_{k=0}^n$$

Let $p_n(x)={\sum }_{i=0}^n{c}_i{x}^i$ then

Coefficients $c_i$ solve linear system of equations

$$\left[\begin{array}{ccccc}1& x_0& x_0^2& \cdots & x_0^n\\ 1& x_1& x_1^2& \cdots & x_1^n\\ ⋮& ⋮& \ddots & \ddots & ⋮\\ 1& x_n& x_n^2& \cdots & x_n^n\end{array}\right]\left[\begin{array}{c}{c}_0\\ c_1\\ ⋮\\ c_n\end{array}\right]=\left[\begin{array}{c}{f}_0\\ f_1\\ ⋮\\ f_n\end{array}\right]$$

where the matrix is called Vandermonde and is non-singular if $\{x_i\}$ are distinct

Orthogonal Matrix

Let $Q$ be a real square matrix then

$Q$ is orthogonal if

$$Q^T=Q^{-1}$$

which holds if and only if

$$Q^{T}Q=I=Q{Q}^T$$

Orthogonality of Product of Orthogonal Matrices

Let $S,T$ be orthogonal matrices then

$$ST\text{ is orthogonal}$$

Proof

As $S,T$ are orthogonal then

$$S^T=S^{-1}\text{ and }{T}^T=T^{-1}$$

Then

$$(ST{)}^T(ST)=T^T{S}^{T}ST=T^T(S^{T}S)T=T^{T}T=I$$

Scalar Inner Product

Let

$$x=\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right]\text{ and }y\left[\begin{array}{c}{y}_1\\ y_2\\ ⋮\\ y_n\end{array}\right]$$

in ${\mathbb{R}}^n$ then

$$x^{T}y=y^{T}x=\sum _{i=1}^n{x}_i{y}_i\in \mathbb{R}$$

Orthogonality of Vectors

Let $x,y\in {\mathbb{R}}^n$ then

$x,y$ are orthogonal if

$$x^{T}y=0$$

Orthogonal Set

Let $\{u_1,u_2,\cdots ,u_r\}$ be a set of vectors where $u_k\in {\mathbb{R}}^n$ for all $k$ then

$\{u_1,u_2,\cdots ,u_r\}$ is a orthogonal set if

$$u_i^T{u}_j=0\text{ for all }i,j\in \{1,2,\cdots ,r\}\text{ where }i\ne j$$

Columns of an Orthogonal Matrix form an Orthogonal Set lemma

Let $Q$ be an orthogonal matrix with columns $q_1,q_2,\cdots ,q_n$ then

$\{q_1,q_2,\cdots ,q_n\}$ is an orthogonal set and an orthonormal basis for ${\mathbb{R}}^n$

Proof

Suppose

$$Q=[q_1\mid q_2\mid \cdots \mid q_n]$$

so $q_j$ is the $j$-th column of $Q$ then

$$Q^{T}Q=I=\left[\begin{array}{c}{q}_1^T\\ q_2^T\\ ⋮\\ q_n^T\end{array}\right]\left[\begin{array}{cccc}{q}_1& q_2& \cdots & q_n\end{array}\right]=\left[\begin{array}{cccc}1& 0& \cdots & 0\\ 0& 1& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & 1\end{array}\right]$$

Comparing $(i,j)$-th entry then

$$q_i^T{q}_j={\delta }_{ij}$$

Hence $\{q_1,q_2,\cdots ,q_n\}$ is an orthonormal set

As $q_i^T{q}_i=1$ then it is also an orthonormal set
Let $x\in {\mathbb{R}}^n$ then

$$x=Q{Q}^{T}x=Qc\text{ where }c=Q^{T}x=$$

Hence

$$x=\sum _{i=1}^n{c}_i{q}_i$$

Orthogonal Matrices don't affect Scalar Product

Let $P$ be a $n\times n$ orthogonal matrix
Let $u\in {\mathbb{R}}^n$

Let $v=Pu$ then

$$u^{T}u=v^{T}v$$

Proof

$$v^{T}v=(Pu{)}^T(PU)=u^T(P^{T}P)u=u^{T}u$$

Outer Product

Let $x,y\in {\mathbb{R}}^n$ then

Outer Product of $x$ and $y$ is

$$x{y}^T=\left[\begin{array}{cccc}{x}_1{y}_1& x_1{y}_2& \cdots & x_1{y}_n\\ x_2{y}_1& x_2{y}_2& \cdots & x_2{y}_n\\ ⋮& ⋮& \ddots & ⋮\\ x_n{y}_1& x_n{y}_2& \cdots & x_n{y}_n\end{array}\right]$$

Householder Matrix

For $w\in {\mathbb{R}}^n$ where $w\ne 0$ then

Household reflector $H(w)\in {\mathbb{R}}^{n\times n}$ is

$$H(w)=I-\frac{2}{w^{T}w}w{w}^T$$

Property of Householder Reflectors

For $w\in {\mathbb{R}}^n$ where $w\ne 0$ then

$H(w)$ is symmetric orthogonal

Proof

Symmetric

$$(H(w){)}^T={\left(I-\frac{2}{w^{T}w}w{w}^T\right)}^T=I^T-\frac{2}{w^{T}w}(w{w}^T{)}^T=I-\frac{2}{w^{T}w}w{w}^T=H(w)$$

Orthogonality

$$\begin{array}{rl}H(w)H(w{)}^T& =\left(I-\frac{2}{w^{T}w}w{w}^T\right)\left(I-\frac{2}{w^{T}w}w{w}^T\right)\\ & =I-\frac{4}{w^{T}w}+\frac{4}{w^{T}w}w(w^{T}w)w^T\\ & =I\end{array}$$

Householder Transformation

Let $u\in {\mathbb{R}}^n$ then

Exists $w\in {\mathbb{R}}^n$ such that

$$H(w)u=\left[\begin{array}{c}\alpha \\ 0\\ ⋮\\ 0\end{array}\right]\equiv v$$

where $\alpha =\pm \sqrt{u^{T}u}$

Proof

As $H(w)$ is orthogonal then $v^{T}v=u^{T}u$ so ${\alpha }^2=u^{T}u$ hence choice of $\alpha$

Let $w=\gamma (u-v)$ where $\gamma \ne 0$ then

$$\begin{array}{rl}{w}^{T}w& ={\gamma }^2(u-v{)}^T(u-v)={\gamma }^2(u^{T}u-2u^{T}v+v^{T}v)\\ & ={\gamma }^2(u^{T}u-2u^{T}v+u^{T}u)\\ & =2\gamma u^T(\gamma (u-v))\\ & =2\gamma w^{T}u\end{array}$$

Hence

$$H(w)u=\left(I-\frac{2}{w^{T}w}w{w}^T\right)u=u-\frac{2w^{T}u}{w^{T}w}w=u-\frac{1}{\gamma }w=u-(u-v)=v$$

Spectral Norm

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

$$||A|{|}_2={\sigma }_1(A)=\underset{x\ne 0}{\max }\frac{||Ax|{|}_2}{||x|{|}_2}$$

where ${\sigma }_1(A)$ is the largest singular value and using Euclidean Norm so

$$||x|{|}_2=\sqrt{x_1^2+x_2^2+\cdots +x_n^2}$$

Low-Rank Approximation

Let $A=U\Sigma V^T$ be the SVD
Let $U=[u_1,\cdots ,u_n]$ and $V=[v_1,\cdots ,v_n]$

Let $r\in \mathbb{N}$ with $r\le n$ then define tall-skinny matrices

$$U_r=[u_1,\cdots ,u_r]\text{ and }{V}_r=[v_1,\cdots ,v_r]\text{ and }{\Sigma }_r=\mathrm{diag}({\sigma }_1,\cdots ,{\sigma }_r)$$

Then define rank-$r$ truncated SVD of $A$ as

$$A_r=U_r{\Sigma }_r{V}_r^T=\sum _{i=1}^r{\sigma }_i{u}_i{v}_i^T$$

with $\mathrm{rank}(A_r)=r$ and $A_{}$

Eigenvalue Decomposition

Let $A\in {\mathbb{R}}^{n\times n}$
Let $A{x}_i={\lambda }_i{x}_i$ for $i=1,\cdots ,n$ where $x_i$ is linearly independent

Define

$$X:=[x_1,x_2,\cdots ,x_n]$$

Then $X$ is non-singular with

$$A=X\Lambda X^{-1}$$

Schur Decomposition

Let $A\in {\mathbb{R}}^{n\times n}$ then

$$A=QT{Q}^{\ast }$$

where

$Q$ is unitary so $Q{Q}^{\ast }=Q^{\ast }Q=I_n$
$T$ is triangular

Similar Matrices

Let $A$ be a symmetric matrix

$A$ is similar to $B$ if there exists non-singular matrix $P$ such that

$$A=P^{-1}BP$$

where $A,B$ have same eigenvalues as

$$0=\det (A-\lambda I)=\det (P^{-1}(B-\lambda I)P)=\det (P^{-1})\det (P)\det (B-\lambda I)=\det (B-\lambda I)$$

Hence

$$\det (A-\lambda I)=0⟺\det (B-\lambda I)=0$$

Tridiagonal

Let $A$ be a matrix then

$A$ is tridiagonal if only non-zero elements are along diagonal, lower diagonal and upper diagonal
So $A$ is in form

$$A=\left(\begin{array}{ccccc}{a}_1& b_1& & & \\ c_1& a_2& b_2& & \\ & c_2& \ddots & \ddots & \\ & & \ddots & \ddots & b_{n-1}\\ & & & c_{n-1}& a_n\end{array}\right)$$

Reduction to Tridiagonal Form

Let $A$ be a matrix then

There exists construction for $Q$ such that

$$QA{Q}^T\text{ is tridiagonal}$$

where $Q$ is orthogonal so a similarity transformation

Proof

If

$$H(w)A=\left[\begin{array}{cccc}\times & \times & \cdots & \times \\ 0& \times & \cdots & \times \\ ⋮& ⋮& \ddots & ⋮\\ 0& \times & \cdots & \times \end{array}\right]$$

Then $H(w)AH(w{)}^T$ is generally full so
All zeroes created by pre-multiplication are destroyed by post-multiplication

Assume $A=A^T$ then $A$ is in form

$$A=\left[\begin{array}{cc}\gamma & u^T\\ u& C\end{array}\right]$$

with

$$w=\left[\begin{array}{c}0\\ \hat{w}\end{array}\right]\text{ where }H(\hat{w})u=\left[\begin{array}{c}\alpha \\ 0\\ ⋮\\ 0\end{array}\right]$$

Then

$$H(w)A=\left[\begin{array}{cccc}\gamma & u^T& & \\ \alpha & \times & \cdots & \times \\ ⋮& ⋮& ⋮& ⋮\\ 0& \times & ⋮& \times \end{array}\right]$$

However

$$H(w)AH(w{)}^{-1}=H(w)AH(w{)}^T=H(w)AH(w)=\left(\begin{array}{ccccc}\gamma & \alpha & 0& \cdots & 0\\ \alpha & & & & \\ 0& & & & \\ ⋮& & B& & \\ 0& & & & \end{array}\right)$$

where

$$B=H(\hat{w})C{H}^T(\hat{w})\text{ as }{u}^{T}H(\hat{w}{)}^T=(\alpha ,0,\cdots ,0)$$

Inductively apply to smaller matrix $B$

After $n-2$ such Householder Similarity Transformations then

$$H(w_{n-2})\cdots H(w_2)H(w)AH(w)H(w_2)\cdots H(w_{n-2})$$

is tridiagonal

Givens Rotation

Let $i,j\in \mathbb{N}$ then

Orthogonal Matrix

$$J(i,j)$$

is defined by
$I$ except for the four elements $(i,i),(i,j),(j,i),(j,j)$ replaced by

$$c,s,-s,c\text{ respectively}$$

where

$$c^2+s^2=1$$

Rotating

Given any vector

$$\left(\begin{array}{c}a\\ b\end{array}\right)$$

Can always find $c,s$ such that

$$\left(\begin{array}{cc}c& s\\ -s& c\end{array}\right)\left(\begin{array}{c}a\\ b\end{array}\right)=\left(\begin{array}{c}\sqrt{a^2+b^2}\\ 0\end{array}\right)$$

Construction of Upper Triangular Matrix

Let $A$ be a matrix then exists orthogonal matrix such that

$$Q^{T}A\text{ is upper triangular}$$

And so $A$ in form

$$A=QR$$

Proof

From Reduction to Tridiagonal Form there exists $Q$ such that

$$QA{Q}^T\text{is tridiagonal}$$

Then using Givens Rotation Matrices choosing $c$ such that

$$\left[\begin{array}{cc}c& s\\ -s& c\end{array}\right]\left[\begin{array}{c}a\\ b\end{array}\right]=\left[\begin{array}{c}\sqrt{a^2+b^2}\\ 0\end{array}\right]$$

So there exists

$$J(n-1,n)\cdots J(2,3)J(1,2)A=R$$

such that $R$ is upper triangular and in form

$$R=\left[\begin{array}{cccccccc}\times & \times & \times & 0& 0& 0& \cdots & 0\\ 0& \times & \times & \times & 0& 0& \cdots & 0\\ 0& 0& \times & \times & \times & 0& \cdots & 0\\ ⋮& ⋮& & & & & & ⋮\\ 0& 0& 0& 0& \times & \times & \times & 0\\ 0& 0& 0& 0& 0& \times & \times & \times \\ 0& 0& 0& 0& 0& 0& \times & \times \\ 0& 0& 0& 0& 0& 0& 0& \times \end{array}\right]$$

QR Algorithm on Symmetric Diagonal Matrix lemma

Let $A$ be a symmetric tridiagonal matrix then

Applying QR Algorithm to $A$ preserves symmetry and tridiagonal form so

$A_k$ is symmetric tridiagonal for all $k$

Proof

As $A_{k+1}=RQ$ is symmetric if $A_k=QR$ is symmetric
If

$$A_k=QR=J(1,2{)}^{T}J(2,3{)}^T\cdots J(n-1,n{)}^{T}R\text{ is tridiagonal}$$

Then

$$A_{k+1}=RQ=RJ(1,2{)}^{T}J(2,3{)}^T\cdots J(n-1,n{)}^T$$

is also tridiagonal

Post multiplication by $J(i,i+1{)}^T$ replaces columns $i$ and $i+1$ by linear combination
With columns $j=1,2,\cdots ,i-1,i+2,\cdots ,n$ being the same

As $R$ is upper triangular then subdiagonal entry $RJ(1,2{)}^T$ is in position $(2,1)$

Similarly,
Subdiagonal entries in $RJ(1,2{)}^{T}J(2,3{)}^T=(RJ(1,2){)}^{T}J(2,3{)}^T$ is position $(2,1)$ and $(3,2)$
Hence inductively

$$\begin{array}{rl}RJ(1,2)& {}^{T}J(2,3{)}^T\cdots J(i-2,i-1{)}^{T}J(i-1,i{)}^T\\ & =(RJ(1,2{)}^{T}J(2,3{)}^T\cdots J(i-2,i-1{)}^T)J(i-1,i{)}^T\end{array}$$

are in positions $(j,j-1)$ for $j=2,\cdots ,i$
Hence lower triangular part of $A_{k+1}$ has non-zeros on first subdiagonal

As $A_{k+1}$ is symmetric then it must be tridiagonal