David. C. Lay: Linear Algebra and its Applications", Addison-Wesley.

5.3 Theorem 5

The Diagonalization Theorem: An $n\times n$ matrix $A$ is diagonalizable if and only if $A$ has $n$ linearly independent eigenvectors.

First, prove that

An $n\times n$ matrix $A$ is diagonalizable $⟹$ $A$ has $n$ linearly independent eigenvectors.

$$A=PD{P}^{-1}$$$$D=\left[\begin{array}{cccc}{\lambda }_1& 0& \cdots & 0\\ 0& {\lambda }_2& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & {\lambda }_n\end{array}\right]$$$$P=\left[\begin{array}{cccc}{\mathbf{v}}_1& {\mathbf{v}}_2& \cdots & {\mathbf{v}}_n\end{array}\right]$$$$\begin{array}{rl}PD& =\left[\begin{array}{cccc}{\mathbf{v}}_1& {\mathbf{v}}_2& \cdots & {\mathbf{v}}_n\end{array}\right]\left[\begin{array}{cccc}{\lambda }_1& 0& \cdots & 0\\ 0& {\lambda }_2& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & {\lambda }_n\end{array}\right]\\ & =\left[\begin{array}{cccc}{\lambda }_1{\mathbf{v}}_1& {\lambda }_2{\mathbf{v}}_2& \cdots & {\lambda }_n{\mathbf{v}}_n\end{array}\right]\end{array}$$$$\begin{array}{rl}A& =A\times I\\ & =A(P{P}^{-1})\\ & =(AP)P^{-1}\\ & =AP{P}^{-1}\end{array}$$$$\begin{array}{rl}AP{P}^{-1}& =PD{P}^{-1}\\ AP{P}^{-1}P& =PD{P}^{-1}P\\ AP(P^{-1}P)& =PD(P^{-1}P)\\ AP\times I& =PD\times I\\ AP& =PD\end{array}$$$$\begin{array}{rl}AP& =A\left[\begin{array}{cccc}{\mathbf{v}}_1& {\mathbf{v}}_2& \cdots & {\mathbf{v}}_n\end{array}\right]\\ & =\left[\begin{array}{cccc}A{\mathbf{v}}_1& A{\mathbf{v}}_2& \cdots & A{\mathbf{v}}_n\end{array}\right]\end{array}$$$$\begin{array}{rl}\left[\begin{array}{cccc}A{\mathbf{v}}_1& A{\mathbf{v}}_2& \cdots & A{\mathbf{v}}_n\end{array}\right]& =\left[\begin{array}{cccc}{\lambda }_1{\mathbf{v}}_1& {\lambda }_2{\mathbf{v}}_2& \cdots & {\lambda }_n{\mathbf{v}}_n\end{array}\right]\\ A{\mathbf{v}}_i& ={\lambda }_i{\mathbf{v}}_i\end{array}$$

${\mathbf{v}}_i$ is the $i$th eigenvactor of $A$ and ${\lambda }_i$ is the corresponding eigenvalue.

Because $P$ is invertible, $\left[\begin{array}{cccc}{\mathbf{v}}_1& {\mathbf{v}}_2& \cdots & {\mathbf{v}}_n\end{array}\right]$ is linearly independent.

Then, prove that

$A$ has $n$ linearly independent eigenvectors $⟹$ An $n\times n$ matrix $A$ is diagonalizable.

Let $A=PB{P}^{-1}$.

$A$ is similar to $B$

Let $B=\left[\begin{array}{cccc}{\lambda }_1& 0& \cdots & 0\\ 0& {\lambda }_2& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & {\lambda }_n\end{array}\right]$

Where ${\lambda }_i$ is the $i$th eigenvalue of $A$.

$A{\mathbf{v}}_i={\lambda }_i{\mathbf{v}}_i$, ${\mathbf{v}}_i$ is the corresponding eigenvector.

$P$ is some matirx. But such $P$ may not exit, resulting $A=PB{P}^{-1}$ is invalid.

So we just need to find a $P$.

Let $P=\left[\begin{array}{cccc}{\mathbf{p}}_1& {\mathbf{p}}_2& \cdots & {\mathbf{p}}_n\end{array}\right]$, where ${\mathbf{p}}_i$ is the $i$the column vector.

$$\begin{array}{rl}PB& =\left[\begin{array}{cccc}{\mathbf{p}}_1& {\mathbf{p}}_2& \cdots & {\mathbf{p}}_n\end{array}\right]\left[\begin{array}{cccc}{\lambda }_1& 0& \cdots & 0\\ 0& {\lambda }_2& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & {\lambda }_n\end{array}\right]\\ & =\left[\begin{array}{cccc}{\lambda }_1{\mathbf{p}}_1& {\lambda }_2{\mathbf{p}}_2& \cdots & {\lambda }_n{\mathbf{p}}_n\end{array}\right]\end{array}$$

Construct the same euqation again.

$$\begin{array}{rl}A& =A\times I\\ & =A(P{P}^{-1})\\ & =(AP)P^{-1}\\ & =AP{P}^{-1}\end{array}$$$$\begin{array}{rl}AP{P}^{-1}& =PB{P}^{-1}\\ AP{P}^{-1}P& =PB{P}^{-1}P\\ AP(P^{-1}P)& =PB(P^{-1}P)\\ AP\times I& =PB\times I\\ AP& =PB\end{array}$$

Let $A=\left[\begin{array}{c}{\mathbf{a}}_1\\ {\mathbf{a}}_2\\ ⋮\\ {\mathbf{a}}_n\end{array}\right]$, where ${\mathbf{a}}_i$ is the $i$the raw vector.

$$\begin{array}{rl}AP& =\left[\begin{array}{c}{\mathbf{a}}_1\\ {\mathbf{a}}_2\\ ⋮\\ {\mathbf{a}}_n\end{array}\right]\left[\begin{array}{cccc}{\mathbf{p}}_1& {\mathbf{p}}_2& \cdots & {\mathbf{p}}_n\end{array}\right]\\ & =\left[\begin{array}{cccc}{\mathbf{a}}_1{\mathbf{p}}_1& {\mathbf{a}}_1{\mathbf{p}}_2& \cdots & {\mathbf{a}}_1{\mathbf{p}}_n\\ {\mathbf{a}}_2{\mathbf{p}}_1& {\mathbf{a}}_2{\mathbf{p}}_2& \cdots & {\mathbf{a}}_2{\mathbf{p}}_n\\ ⋮& ⋮& \ddots & ⋮\\ {\mathbf{a}}_n{\mathbf{p}}_1& {\mathbf{a}}_n{\mathbf{p}}_2& \cdots & {\mathbf{a}}_n{\mathbf{p}}_n\end{array}\right]\end{array}$$$$\begin{array}{rl}AP& =PB\\ \left[\begin{array}{cccc}{\mathbf{a}}_1{\mathbf{p}}_1& {\mathbf{a}}_1{\mathbf{p}}_2& \cdots & {\mathbf{a}}_1{\mathbf{p}}_n\\ {\mathbf{a}}_2{\mathbf{p}}_1& {\mathbf{a}}_2{\mathbf{p}}_2& \cdots & {\mathbf{a}}_2{\mathbf{p}}_n\\ ⋮& ⋮& \ddots & ⋮\\ {\mathbf{a}}_n{\mathbf{p}}_1& {\mathbf{a}}_n{\mathbf{p}}_2& \cdots & {\mathbf{a}}_n{\mathbf{p}}_n\end{array}\right]& =\left[\begin{array}{cccc}{\lambda }_1{\mathbf{p}}_1& {\lambda }_2{\mathbf{p}}_2& \cdots & {\lambda }_n{\mathbf{p}}_n\end{array}\right]\\ \left[\begin{array}{c}{\mathbf{a}}_1{\mathbf{p}}_i\\ {\mathbf{a}}_2{\mathbf{p}}_i\\ ⋮\\ {\mathbf{a}}_n{\mathbf{p}}_i\end{array}\right]& ={\lambda }_i{\mathbf{p}}_i\end{array}$$

Let ${\mathbf{a}}_i=\left[\begin{array}{cccc}{a}_{i1}& a_{i2}& \cdots & a_{in}\end{array}\right]$.

Let ${\mathbf{p}}_i=\left[\begin{array}{c}{p}_{1i}\\ p_{2i}\\ \cdots \\ p_{ni}\end{array}\right]$.

$${\mathbf{a}}_j{\mathbf{p}}_i=\left[\begin{array}{cccc}{a}_{j1}& a_{j2}& \cdots & a_{jn}\end{array}\right]\left[\begin{array}{c}{p}_{1i}\\ p_{2i}\\ \cdots \\ p_{ni}\end{array}\right]$$

By the definition of matrix multiplication,

$$\begin{array}{rl}\left[\begin{array}{c}{\mathbf{a}}_1{\mathbf{p}}_i\\ {\mathbf{a}}_2{\mathbf{p}}_i\\ ⋮\\ {\mathbf{a}}_n{\mathbf{p}}_i\end{array}\right]& =\left[\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}& a_{n2}& \cdots & a_{nn}\end{array}\right]\left[\begin{array}{c}{p}_{1i}\\ p_{2i}\\ \cdots \\ p_{ni}\end{array}\right]\\ & =\left[\begin{array}{c}{\mathbf{a}}_1\\ {\mathbf{a}}_2\\ ⋮\\ {\mathbf{a}}_n\end{array}\right]{\mathbf{P}}_i\\ & =A{\mathbf{p}}_i\end{array}$$$$A{\mathbf{p}}_i={\lambda }_i{\mathbf{p}}_i$$

Thus, each $\mathbf{p}$ is an eigenvector of $A$.

Because $n$ eigenvectors of $A$ are linearly independet, $P$ is invertible.

$A=PB{P}^{-1}$ is indeed valid.

6.1 Theorem 3

Let $A$ be an $m\times n$ matrix. The orthogonal complement of the row space of $A$ is the null space of $A$, and the orthogonal complement of the column space of $A$ is the null space of $A^T$ : $(\text{Row}A{)}^{\perp }=\text{Nul}A$ and $(\text{Col}A{)}^{\perp }=\text{Nul}{A}^T$

Let $A=\left[\begin{array}{c}{\mathbf{a}}_1\\ {\mathbf{a}}_2\\ ⋮\\ {\mathbf{a}}_n\end{array}\right]$, and $\mathbf{x}\in \text{Nul}A$.

By the definition of Null Space,

$$\begin{array}{rl}A\mathbf{\text{x}}& =\mathbf{\text{0}}\\ \left[\begin{array}{c}{\mathbf{a}}_1\\ {\mathbf{a}}_2\\ ⋮\\ {\mathbf{a}}_n\end{array}\right]\mathbf{\text{x}}& =\left[\begin{array}{c}0\\ 0\\ ⋮\\ 0\end{array}\right]\end{array}$$$${\mathbf{a}}_i\mathbf{x}=0$$

Because ${\mathbf{a}}_i$ is the row vector and $\mathbf{x}$ is the column vector, ${\mathbf{a}}_i\mathbf{x}$ is the the inner product of the row vector and any vector from Null Space, resulting the linear combinations of row vector are also perpendicular to Null Space.

Thus, $\text{Row}A=(\text{Nul}A{)}^{\perp }$, namely $(\text{Row}A{)}^{\perp }=\text{Nul}A$.

And we can get $(\text{Col}A{)}^{\perp }=\text{Nul}{A}^T$, by transposing both sides.

6.2 Theorem 7

Let $U$ be an $m\times n$ matrix with orthonormal columns, and let $x$ and $y$ be in ${\mathbb{R}}^n$. Then

a. $\Vert U\mathbf{x}\Vert =\Vert \mathbf{x}\Vert$

$$\begin{array}{rl}\Vert U\mathbf{x}\Vert & =\sqrt{U\mathbf{x}\mathbf{\cdot }U\mathbf{x}}\\ & =\sqrt{(U\mathbf{x}{)}^{T}U\mathbf{x}}\\ & =\sqrt{{\mathbf{x}}^T{U}^{T}U\mathbf{x}}\\ & =\sqrt{{\mathbf{x}}^T(U^{T}U)\mathbf{x}}\\ & =\sqrt{{\mathbf{x}}^{T}I\mathbf{x}}\\ & =\sqrt{{\mathbf{x}}^T\mathbf{x}}\end{array}$$$$\begin{array}{rl}\Vert \mathbf{x}\Vert & =\sqrt{\mathbf{x}\mathbf{\cdot }\mathbf{x}}\\ & =\sqrt{{\mathbf{x}}^T\mathbf{x}}\end{array}$$

b. $(U\mathbf{x})\mathbf{\cdot }(U\mathbf{y})=\mathbf{x}\mathbf{\cdot }\mathbf{y}$

$$\begin{array}{rl}(U\mathbf{x})\mathbf{\cdot }(U\mathbf{y})& =(U\mathbf{x}{)}^T(U\mathbf{y})\\ & ={\mathbf{x}}^T{U}^{T}U\mathbf{y}\\ & ={\mathbf{x}}^T(U^{T}U)\mathbf{y}\\ & ={\mathbf{x}}^{T}I\mathbf{y}\\ & ={\mathbf{x}}^T\mathbf{y}\end{array}$$$$\begin{array}{rl}\mathbf{x}\mathbf{\cdot }\mathbf{y}& ={\mathbf{x}}^T\mathbf{y}\end{array}$$

c. $(U\mathbf{x})\mathbf{\cdot }(U\mathbf{y})=0⟺\mathbf{x}\mathbf{\cdot }\mathbf{y}=0$

This is just a special case of b.

6.3 Theorem 8

The Orthogonal Decomposition Theorem: Let $W$ be a subspace of ${\mathbb{R}}^n$. Then each $\mathbf{y}$ in ${\mathbb{R}}^n$ can be written uniquely in the form $\mathbf{y}=\hat{\mathbf{y}}+\mathbf{z}$ (1) where $\hat{\mathbf{y}}$ is in $W$ and $z$ is in $W^{\perp }$. In fact, if $\{{\mathbf{u}}_1,\dots ,{\mathbf{u}}_p\}$ is any orthogonal basis of $W$ , then $\hat{\mathbf{y}}=\frac{\mathbf{y}\mathbf{\cdot }{\mathbf{u}}_1}{{\mathbf{u}}_1\mathbf{\cdot }{\mathbf{u}}_1}{\mathbf{u}}_1+\dots +\frac{\mathbf{y}\mathbf{\cdot }{\mathbf{u}}_p}{{\mathbf{u}}_p\mathbf{\cdot }{\mathbf{u}}_p}{\mathbf{u}}_p$ (2) and $\mathbf{z}=\mathbf{y}-\hat{\mathbf{y}}$.

The textbook provides the proof. Therefore, we only show how to derive formula (2) here.

$$\begin{array}{rl}(\mathbf{y}-\hat{\mathbf{y}})\mathbf{\cdot }\hat{\mathbf{y}}& =0\\ \mathbf{y}\mathbf{\cdot }\hat{\mathbf{y}}-\hat{\mathbf{y}}\mathbf{\cdot }\hat{\mathbf{y}}& =0\\ \mathbf{y}\mathbf{\cdot }\hat{\mathbf{y}}& =\hat{\mathbf{y}}\mathbf{\cdot }\hat{\mathbf{y}}\end{array}$$

Let $\hat{\mathbf{y}}=c_1{\mathbf{u}}_1+\cdots +c_p{\mathbf{u}}_p$.

Namely,

$$\begin{array}{rl}\hat{\mathbf{y}}& =\left[\begin{array}{cccc}{\mathbf{u}}_1& {\mathbf{u}}_2& \cdots & {\mathbf{u}}_p\end{array}\right]\left[\begin{array}{c}{c}_1\\ c_2\\ ⋮\\ c_p\end{array}\right]\end{array}$$$$\begin{array}{rl}\mathbf{y}\mathbf{\cdot }\hat{\mathbf{y}}=& {\mathbf{y}}^T\hat{\mathbf{y}}\\ =& {\mathbf{y}}^T\left[\begin{array}{cccc}{\mathbf{u}}_1& {\mathbf{u}}_2& \cdots & {\mathbf{u}}_p\end{array}\right]\left[\begin{array}{c}{c}_1\\ c_2\\ ⋮\\ c_p\end{array}\right]\end{array}$$$$\begin{array}{rl}\hat{\mathbf{y}}\mathbf{\cdot }\hat{\mathbf{y}}=& (c_1{\mathbf{u}}_1+\cdots +c_p{\mathbf{u}}_p)\mathbf{\cdot }(c_1{\mathbf{u}}_1+\cdots +c_p{\mathbf{u}}_p)\\ =& (c_1{)}^2{\mathbf{u}}_1\mathbf{\cdot }{\mathbf{u}}_1+\cdots +(c_p{)}^2{\mathbf{u}}_p\mathbf{\cdot }{\mathbf{u}}_p\\ =& \left[\begin{array}{ccc}{c}_1({\mathbf{u}}_1\mathbf{\cdot }{\mathbf{u}}_1)& \cdots & c_p({\mathbf{u}}_p\mathbf{\cdot }{\mathbf{u}}_p)\end{array}\right]\left[\begin{array}{c}{c}_1\\ c_2\\ ⋮\\ c_p\end{array}\right]\end{array}$$

Apply $\mathbf{y}\mathbf{\cdot }\hat{\mathbf{y}}=\hat{\mathbf{y}}\mathbf{\cdot }\hat{\mathbf{y}}$:

$$\begin{array}{rl}& {\mathbf{y}}^T\left[\begin{array}{cccc}{\mathbf{u}}_1& {\mathbf{u}}_2& \cdots & {\mathbf{u}}_p\end{array}\right]\left[\begin{array}{c}{c}_1\\ c_2\\ ⋮\\ c_p\end{array}\right]\\ =& \left[\begin{array}{cccc}{c}_1({\mathbf{u}}_1\mathbf{\cdot }{\mathbf{u}}_1)& \cdots & c_p({\mathbf{u}}_p\mathbf{\cdot }{\mathbf{u}}_p)& \end{array}\right]\left[\begin{array}{c}{c}_1\\ c_2\\ ⋮\\ c_p\end{array}\right]\\ & {\mathbf{y}}^T\left[\begin{array}{cccc}{\mathbf{u}}_1& {\mathbf{u}}_2& \cdots & {\mathbf{u}}_p\end{array}\right]\\ =& \left[\begin{array}{ccc}{c}_1({\mathbf{u}}_1\mathbf{\cdot }{\mathbf{u}}_1)& \cdots & c_p({\mathbf{u}}_p\mathbf{\cdot }{\mathbf{u}}_p)\end{array}\right]\end{array}$$

By the definition of matrix multiplication,

$$\begin{array}{rl}{c}_i({\mathbf{u}}_i\mathbf{\cdot }{\mathbf{u}}_i)& ={\mathbf{y}}^T{\mathbf{u}}_i\\ & =\mathbf{y}\mathbf{\cdot }{\mathbf{u}}_i\\ c_i& =\frac{\mathbf{y}\mathbf{\cdot }{\mathbf{u}}_i}{{\mathbf{u}}_i\mathbf{\cdot }{\mathbf{u}}_i}\end{array}$$

$i$ ranges from $1$ to $p$.

6.5 Theorem 15

Given an $m\times n$ matrix $A$ with linearly independent columns, let $A=QR$ be a QR factorization of A as in Theorem 12. Then, for each $\mathbf{b}$ in ${\mathbb{R}}^m$, the equation $A\mathbf{x}=\mathbf{b}$ has a unique least-squares solution, given by $\hat{\mathbf{x}}=R^{-1}{Q}^T\hat{\mathbf{b}}$

The textbook provides the proof. We only show how to derive formula (6) here.

$$\begin{array}{rl}A\hat{\mathbf{x}}=& \hat{\mathbf{b}}\\ (QR)\hat{\mathbf{x}}=& \hat{\mathbf{b}}\\ (QR{)}^{-1}(QR)\hat{\mathbf{x}}=& (QR{)}^{-1}\hat{\mathbf{b}}\\ I\hat{\mathbf{x}}=& R^{-1}{Q}^{-1}\hat{\mathbf{b}}\\ \hat{\mathbf{x}}=& R^{-1}{Q}^T\hat{\mathbf{b}}\end{array}$$

Because $Q$ has orthonormal columns,

$$\begin{array}{r}{Q}^{T}Q=I=Q^{-1}Q\\ Q^T=Q^{-1}\end{array}$$