# Revisit the Fundamental Theorem of Linear Algebra

Jun Lu<EMAIL_ADDRESS>
###### Abstract

This survey is meant to provide an introduction to the fundamental theorem of
linear algebra and the theories behind them. Our goal is to give a rigorous
introduction to the readers with prior exposure to linear algebra.
Specifically, we provide some details and proofs of some results from (Strang,
1993). We then describe the fundamental theorem of linear algebra from
different views and find the properties and relationships behind the views.
The fundamental theorem of linear algebra is essential in many fields, such as
electrical engineering, computer science, machine learning and, deep learning.
This survey is primarily a summary of purpose, significance of important
theories behind it.

The sole aim of this survey is to give a self-contained introduction to
concepts and mathematical tools in theory behind the fundamental theorem of
linear algebra and rigorous analysis in order to seamlessly introduce its
properties in four subspaces in subsequent sections. However, we clearly
realize our inability to cover all the useful and interesting results and
given the paucity of scope to present this discussion, e.g., the separated
analysis of the (orthogonal) projection matrices. We refer the reader to
literature in the field of linear algebra for a more detailed introduction to
the related fields. Some excellent examples include (Rose, 1982; Strang, 2009;
Trefethen and Bau III, 1997; Strang, 2019, 2021).

Keywords: Fundamental theory of linear algebra, Four subspaces, SVD, Least
squares, One-sided inverse, g-inverse, reflexive g-inverse, Pseudo-inverse.

###### Contents

  1. 1 Introduction and Background
  2. 2 Fundamental Theorem of Linear Algebra
    1. 2.1 Dimension of Column Space and Row Space
    2. 2.2 Fundamental Theorem of Linear Algebra
  3. 3 SVD in the Fundamental Theorem of Linear Algebra
  4. 4 Least Squares in the Fundamental Theorem of Linear Algebra
  5. 5 Least Squares via the Full SVD for Rank Deficient Matrices
  6. 6 Pseudo-Inverse in the Fundamental Theorem of Linear Algebra
    1. 6.1 One-sided Inverse
    2. 6.2 Generalized Inverse (g-inverse)
    3. 6.3 Reflexive Generalized Inverse (rg-inverse)
    4. 6.4 Pseudo-Inverse
    5. 6.5 Pseudo-Inverse in SVD
  7. A Rank of a Special Symmetric Matrix
  8. B Similar Matrices
  9. C Properties of Symmetric and Idempotent Matrices
  10. D Spectral Decomposition (Theorem)
  11. E Singular Value Decomposition (SVD)

##  1 Introduction and Background

The readers with enough background of matrix analysis can skip this section.
In all cases, scalars will be denoted in a non-bold font possibly with
subscripts (e.g., $a$, $\alpha$, $\alpha_{i}$). We will use bold face lower
case letters possibly with subscripts to denote vectors (e.g.,
$\boldsymbol{\mu}$, $\bm{x}$, $\bm{x}_{n}$, $\bm{z}$) and bold face upper case
letters possibly with subscripts to denote matrices (e.g., $\bm{A}$,
$\bm{L}_{j}$). The $i$-th element of a vector $\bm{z}$ will be denoted by
$\bm{z}_{i}$ in bold font. The $i$-th row and $j$-th column element of matrix
$\bm{A}$ will be denoted by $\bm{A}_{ij}$. Furthermore, it will be helpful to
utilize the Matlab-style notation, the $i$-th row to $j$-th row and $k$-th
column to $m$-th column submatrix of matrix $\bm{A}$ will be denoted by
$\bm{A}_{i:j,k:m}$. And in all cases, vectors are formulated in a column
rather than in a row. A row vector will be denoted by a transpose of a column
vector such as $\bm{a}^{\top}$. A specific column vector with values are split
by symbol $";"$, e.g., $\bm{x}=[1;2;3]$ is a column vector in 3. Similarly, a
specific row vector with values are split by symbol $","$, e.g.,
$\bm{y}=[1,2,3]$ is a row vector with 3 values. Further, a column vector can
be denoted by the transpose of a row vector e.g., $\bm{y}=[1,2,3]^{\top}$ is a
column vector.

The transpose of a matrix $\bm{A}$ will be denoted by $\bm{A}^{\top}$ and its
inverse will be denoted by $\bm{A}^{-1}$ . We will denote the $p\times p$
identity matrix by $\bm{I}_{p}$. A vector or matrix of all zeros will be
denoted by a bold face zero $\boldsymbol{0}$ whose size should be clear from
context, or we denote $\boldsymbol{0}_{p}$ to be the vector of all zeros with
$p$ entries.

######  Definition 1 (Eigenvalue)

Given any vector space $E$ and any linear map $A:E\rightarrow E$, a scalar
$\lambda\in K$ is called an eigenvalue, or proper value, or characteristic
value of $\bm{A}$ if there is some nonzero vector $\bm{u}\in E$ such that

$\bm{A}\bm{u}=\lambda\bm{u}.$

######  Definition 2 (Eigenvector)

A vector $\bm{u}\in E$ is called an eigenvector, or proper vector, or
characteristic vector of $\bm{A}$ if $\bm{u}\neq 0$ and if there is some
$\lambda\in K$ such that

$\bm{A}\bm{u}=\lambda\bm{u},$

where the scalar $\lambda$ is then an eigenvalue. And we say that $\bm{u}$ is
an eigenvector associated with $\lambda$.

######  Definition 3 (Linearly Independent)

A set of vectors $\\{\bm{a}_{1},\bm{a}_{2},\cdots,\bm{a}_{n}\\}$ is called
linearly independent if there is no combination can get
$x_{1}\bm{a}_{1}+x_{2}\bm{a}_{2}+\cdots+x_{n}\bm{a}_{n}=0$ except all
$x_{i}$’s are zero. An equivalent definition is that
$\bm{a}_{1}\neq\boldsymbol{0}$, and for every $k>1$, the vector $\bm{a}_{k}$
does not belong to the span of $\bm{a}_{1},\bm{a}_{2},\cdots,\bm{a}_{k-1}$.

In the study of linear algebra, every vector space has a basis and every
vector is a linear combination of members of the basis. We then define span
and dimension of subspace via the basis.

######  Definition 4 (Span)

If every vector $\bm{v}$ in subspace $\mathcal{V}$ can be expressed as a
linear combination of $\\{\bm{a}_{1},\bm{a}_{2},\cdots,\bm{a}_{k}\\}$, then
$\\{\bm{a}_{1},\bm{a}_{2},\cdots,\bm{a}_{k}\\}$ is said to span $\mathcal{V}$.

######  Definition 5 (Basis and Dimension)

A set of vectors $\\{\bm{a}_{1},\bm{a}_{2},\cdots,\bm{a}_{k}\\}$ is called a
basis of $\mathcal{V}$ if they are linearly independent and span
$\mathcal{V}$. Every basis of a given subspace has the same number of vectors,
and the number of vectors in any basis is called the dimension of the subspace
$\mathcal{V}$. By convention, the subspace $\\{\boldsymbol{0}\\}$ is said to
have dimension zero. Furthermore, every subspace of nonzero dimension has a
basis that is orthogonal, i.e., the basis of a subspace can be chosen
orthogonal.

######  Definition 6 (Column Space (Range))

If $\bm{A}$ is an $n\times p$ real matrix, we define the column space (or
range) of $\bm{A}$ to be the set spanned by its columns:

$\mathcal{C}(\bm{A})=\\{\bm{y}\in\mathbb{R}^{n}:\exists\bm{x}\in\mathbb{R}^{p},\,\bm{y}=\bm{A}\bm{x}\\}.$

And the row space of $\bm{A}$ is the set spanned by its rows, which is equal
to the column space of $\bm{A}^{\top}$:

$\mathcal{C}(\bm{A}^{\top})=\\{\bm{x}\in\mathbb{R}^{p}:\exists\bm{y}\in\mathbb{R}^{n},\,\bm{x}=\bm{A}^{\top}\bm{y}\\}.$

######  Definition 7 (Null Space (Kernel))

If $\bm{A}$ is an $n\times p$ real matrix, we define the null space (or
kernel) of $\bm{A}$ to be the set:

$\mathcal{N}(\bm{A})=\\{\bm{y}\in\mathbb{R}^{p}:\,\bm{A}\bm{y}=\boldsymbol{0}\\}.$

And the null space of $\bm{A}^{\top}$ is defined as

$\mathcal{N}(\bm{A}^{\top})=\\{\bm{x}\in\mathbb{R}^{n}:\,\bm{A}^{\top}\bm{x}=\boldsymbol{0}\\}.$

Both the column space of $\bm{A}$ and the null space of $\bm{A}^{\top}$ are
subspaces of p. In fact, every vector in $\mathcal{N}(\bm{A}^{\top})$ is
perpendicular to $\mathcal{C}(\bm{A})$ and vice versa.111Every vector in
$\mathcal{N}(\bm{A})$ is also perpendicular to $\mathcal{C}(\bm{A}^{\top})$
and vice versa.

######  Definition 8 (Rank)

The $rank$ of a matrix $\bm{A}\in^{n\times p}$ is the dimension of the column
space of $\bm{A}$. The rank of $\bm{A}$ is equal to the maximal number of
linearly independent columns of $\bm{A}$, and is also the maximal number of
linearly independent rows of $\bm{A}$. The matrix $\bm{A}$ and its transpose
$\bm{A}^{\top}$ have the same rank. We say that $\bm{A}$ has full rank, if its
rank is equal to $min\\{n,p\\}$. In another word, this is true if and only if
either all the columns of $\bm{A}$ are linearly independent, or all the rows
of $\bm{A}$ are linearly independent. Specifically, given a vector
$\bm{u}\in^{n}$ and a vector $\bm{v}\in^{p}$, then the $n\times p$ matrix
$\bm{u}\bm{v}^{\top}$ is of rank 1.

######  Definition 9 (Orthogonal Complement in General)

The orthogonal complement $\mathcal{V}^{\perp}$ of a subspace $\mathcal{V}$
contains every vector that is perpendicular to $\mathcal{V}$. That is,

$\mathcal{V}^{\perp}=\\{\bm{v}|\bm{v}^{\top}\bm{u}=0,\,\,\,\forall\bm{u}\in\mathcal{V}\\}.$

The two subspaces are disjoint that span the entire space. The dimensions of
$\mathcal{V}$ and $\mathcal{V}^{\perp}$ add to the dimension of the whole
space. Furthermore, $(\mathcal{V}^{\perp})^{\perp}=\mathcal{V}$.

######  Definition 10 (Orthogonal Complement of Column Space)

If $\bm{A}$ is an $n\times p$ real matrix, the orthogonal complement of
$\mathcal{C}(\bm{A})$, $\mathcal{C}^{\bot}(\bm{A})$ is the subspace defined
as:

$\displaystyle\mathcal{C}^{\bot}(\bm{A})$
$\displaystyle=\\{\bm{y}\in\mathbb{R}^{n}:\,\bm{y}^{\top}\bm{A}\bm{x}=\boldsymbol{0},\,\forall\bm{x}\in\mathbb{R}^{p}\\}$
$\displaystyle=\\{\bm{y}\in\mathbb{R}^{n}:\,\bm{y}^{\top}\bm{v}=\boldsymbol{0},\,\forall\bm{v}\in\mathcal{C}(\bm{A})\\}.$

######  Definition 11 (Orthogonal Matrix)

A real square matrix $\bm{Q}$ is an orthogonal matrix if the inverse of
$\bm{Q}$ equals to the transpose of $\bm{Q}$, that is
$\bm{Q}^{-1}=\bm{Q}^{\top}$ and
$\bm{Q}\bm{Q}^{\top}=\bm{Q}^{\top}\bm{Q}=\bm{I}$. In another word, suppose
$\bm{Q}=[\bm{q}_{1},\bm{q}_{2},\cdots,\bm{q}_{n}]$ where $\bm{q}_{i}\in^{n}$
for all $i\in\\{1,2,\cdots,n\\}$, then
$\bm{q}_{i}^{\top}\bm{q}_{j}=\delta(i,j)$ with $\delta(i,j)$ being the
Kronecker delta function. If $\bm{Q}$ contains only $\gamma$ of these columns
with $\gamma<n$, then $\bm{Q}^{\top}\bm{Q}=\bm{I}_{\gamma}$ stills holds with
$\bm{I}_{\gamma}$ being the $\gamma\times\gamma$ identity matrix. But
$\bm{Q}\bm{Q}^{\top}=\bm{I}$ will not be true.

##  2 Fundamental Theorem of Linear Algebra

###  2.1 Dimension of Column Space and Row Space

In this section, we prove Lemma 12 that the dimension of the column space of a
matrix $\bm{X}\in^{n\times p}$ is equal to the dimension of its row space,
i.e., the row rank and the column rank of a matrix $\bm{X}$ are equal.

######  Lemma 12 (Dimension of Column Space and Row Space)

The dimension of the column space of a matrix $\bm{X}\in^{n\times p}$ is equal
to the dimension of its row space, i.e., the row rank and the column rank of a
matrix $\bm{X}$ are equal.

Proof [of Lemma 12] We first notice that the null space of $\bm{X}$ is
orthogonal complementary to the row space of $\bm{X}$:
$\mathcal{N}(\bm{X})\bot\mathcal{C}(\bm{X}^{\top})$ (where the row space of
$\bm{X}$ is exactly the column space of $\bm{X}^{\top}$), that is, vectors in
the null space of $\bm{X}$ are orthogonal to vectors in the row space of
$\bm{X}$. To see this, suppose $\bm{X}$ has rows
$\bm{a}_{1}^{\top},\bm{a}_{2}^{\top},\cdots,\bm{a}_{n}^{\top}$ and
$\bm{X}=[\bm{a}_{1}^{\top};\bm{a}_{2}^{\top};\cdots;\bm{a}_{n}^{\top}]$. For
any vector $\boldsymbol{\beta}\in\mathcal{N}(\bm{X})$, we have
$\bm{X}\boldsymbol{\beta}=\boldsymbol{0}$, that is,
$[\bm{a}_{1}^{\top}\boldsymbol{\beta};\bm{a}_{2}^{\top}\boldsymbol{\beta};\cdots;\bm{a}_{n}^{\top}\boldsymbol{\beta}]=\boldsymbol{0}$.
And since the row space of $\bm{X}$ is spanned by
$\bm{a}_{1}^{\top},\bm{a}_{2}^{\top},\cdots,\bm{a}_{n}^{\top}$. Then
$\boldsymbol{\beta}$ is perpendicular to any vectors from
$\mathcal{C}(\bm{X}^{\top})$ which means
$\mathcal{N}(\bm{X})\bot\mathcal{C}(\bm{X}^{\top})$.

Now suppose, the dimension of the row space of $\bm{X}$ is $r$. Let
$\bm{r}_{1},\bm{r}_{2},\cdots,\bm{r}_{r}$ be a set of vectors in n and form a
basis for the row space. Then the $r$ vectors
$\bm{X}\bm{r}_{1},\bm{X}\bm{r}_{2},\cdots,\bm{X}\bm{r}_{r}$ are in the column
space of $\bm{X}$, furthermore, they are linearly independent. To see this,
suppose we have a linear combination of the $r$ vectors:
$\beta_{1}\bm{A}\bm{r}_{1}+\beta_{2}\bm{A}\bm{r}_{2}+\cdots+\beta_{r}\bm{A}\bm{r}_{r}=0$,
that is,
$\bm{X}(\beta_{1}\bm{r}_{1}+\beta_{2}\bm{r}_{2}+\cdots+\beta_{r}\bm{r}_{r})=0$
and the vector
$\bm{v}=\beta_{1}\bm{r}_{1}+\beta_{2}\bm{r}_{2}+\cdots+\beta_{r}\bm{r}_{r}$ is
in the null space of $\bm{X}$. But since
$\\{\bm{r}_{1},\bm{r}_{2},\cdots,\bm{r}_{r}\\}$ is a basis for the row space
of $\bm{X}$, $\bm{v}$ is thus also in the row space of $\bm{X}$. We have shown
that vectors from the null space of $\bm{X}$ is perpendicular to vectors from
row space of $\bm{X}$, thus $\bm{v}^{\top}\bm{v}=0$ and
$\beta_{1}=\beta_{2}=\cdots=\beta_{r}=0$. Then
$\bm{X}\bm{r}_{1},\bm{X}\bm{r}_{2},\cdots,\bm{X}\bm{r}_{r}$ are in the column
space of $\bm{X}$ and they are independent which means column space of
$\bm{X}$ is larger than $r$. This result shows that row rank of $\bm{X}\leq$
column rank of $\bm{X}$.

If we apply this process again for $\bm{X}^{\top}$. We will have column rank
of $\bm{X}\leq$ row rank of $\bm{X}$. We complete the proof.

A further information can be drawn from this proof is that if
$\\{\bm{r}_{1},\bm{r}_{2},\cdots,\bm{r}_{r}\\}$ is a set of vectors in p that
forms a basis for the row space, then
$\\{\bm{X}\bm{r}_{1},\bm{X}\bm{r}_{2},\cdots,\bm{X}\bm{r}_{r}\\}$ is a basis
for the column space of $\bm{X}$. We formulate this finding into the following
lemma.

######  Lemma 13 (Column Basis from Row Basis)

For any matrix $\bm{X}\in^{n\times p}$, let
$\\{\bm{r}_{1},\bm{r}_{2},\cdots,\bm{r}_{r}\\}$ be a set of vectors in p which
forms a basis for the row space, then
$\\{\bm{X}\bm{r}_{1},\bm{X}\bm{r}_{2},\cdots,\bm{X}\bm{r}_{r}\\}$ is a basis
for the column space of $\bm{X}$.

###  2.2 Fundamental Theorem of Linear Algebra

Figure 1: First Figure: Two pairs of orthogonal subspaces in p and n.
$\dim(\mathcal{C}(\bm{X}^{\top}))+\dim(\mathcal{N}(\bm{X}))=p$ and
$dim(\mathcal{N}(\bm{X}^{\top}))+dim(\mathcal{C}(\bm{X}))=n$. The null space
component goes to zero as
$\bm{X}\boldsymbol{\beta}_{\bm{n}}=\boldsymbol{0}\in^{n}$. The row space
component goes to the column space as
$\bm{X}\boldsymbol{\beta}_{\bm{r}}=\bm{X}(\boldsymbol{\beta}_{\bm{r}}+\boldsymbol{\beta}_{\bm{n}})=\bm{y}\in\mathcal{C}(\bm{X})$.

As a recap, for any matrix $\bm{X}\in^{n\times p}$, it can be easily verified
that any vector in the row space of $\bm{X}$ is perpendicular to any vector in
the null space of $\bm{X}$. Suppose
$\boldsymbol{\beta}_{n}\in\mathcal{N}(\bm{X})$, then
$\bm{X}\boldsymbol{\beta}_{n}=\boldsymbol{0}$ such that
$\boldsymbol{\beta}_{n}$ is perpendicular to every row of $\bm{X}$ which
agrees with our claim.

Similarly, we can also show that any vector in the column space of $\bm{X}$ is
perpendicular to any vector in the null space of $\bm{X}^{\top}$. Furthermore,
the column space of $\bm{X}$ and the null space of $\bm{X}^{\top}$ span the
whole n space which is known as the fundamental theorem of linear algebra.

The fundamental theorem contains two parts, the dimension of the subspaces and
the orthogonality of the subspaces. The orthogonality can be easily verified
as we have shown in the beginning of this section. When the row space has
dimension $r$, the null space has dimension $p-r$. This cannot be easily
stated and the proof of the above theorem is provided as follows.

######  Theorem 14 (Fundamental Theorem of Linear Algebra)

Orthogonal Complement and Rank-Nullity Theorem: for any matrix
$\bm{X}\in^{n\times p}$, we have

$\bullet$ $\mathcal{N}(\bm{X})$ is orthogonal complement to the row space
$\mathcal{C}(\bm{X}^{\top})$ in p:
$dim(\mathcal{N}(\bm{X}))+dim(\mathcal{C}(\bm{X}^{\top}))=p$;

$\bullet$ $\mathcal{N}(\bm{X}^{\top})$ is orthogonal complement to the column
space $\mathcal{C}(\bm{X})$ in n:
$dim(\mathcal{N}(\bm{X}^{\top}))+dim(\mathcal{C}(\bm{X}))=n$;

$\bullet$ For rank-$r$ matrix $\bm{X}$,
$dim(\mathcal{C}(\bm{X}^{\top}))=dim(\mathcal{C}(\bm{X}))=r$, that is,
$dim(\mathcal{N}(\bm{X}))=p-r$ and $dim(\mathcal{N}(\bm{X}^{\top}))=n-r$.

Proof [of Theorem 14] Follow from the proof of Lemma 12 in Section 2.1. Let
$\\{\bm{r}_{1},\bm{r}_{2},\cdots,\bm{r}_{r}\\}$ be a set of vectors in p that
form a basis for the row space, then
$\\{\bm{X}\bm{r}_{1},\bm{X}\bm{r}_{2},\cdots,\bm{X}\bm{r}_{r}\\}$ is a basis
for the column space of $\bm{X}$. Let
$\bm{n}_{1},\bm{n}_{2},\cdots,\bm{n}_{k}\in^{p}$ form a basis for the null
space of $\bm{X}$. Follow again from the proof of Lemma 12,
$\mathcal{N}(\bm{X})\bot\mathcal{C}(\bm{X}^{\top})$, thus,
$\bm{r}_{1},\bm{r}_{2},\cdots,\bm{r}_{r}$ are perpendicular to
$\bm{n}_{1},\bm{n}_{2},\cdots,\bm{n}_{k}$. Then,
$\\{\bm{r}_{1},\bm{r}_{2},\cdots,\bm{r}_{r},\bm{n}_{1},\bm{n}_{2},\cdots,\bm{n}_{k}\\}$
is linearly independent in p.

For any vector $\boldsymbol{\beta}\in^{p}$, $\bm{X}\boldsymbol{\beta}$ is in
the column space of $\bm{X}$. Then it can be expressed by a combination of
$\bm{X}\bm{r}_{1},\bm{X}\bm{r}_{2},\cdots,\bm{X}\bm{r}_{r}$:
$\bm{X}\boldsymbol{\beta}=\sum_{i=1}^{r}a_{i}\bm{X}\bm{r}_{i}$ which states
that $\bm{X}(\boldsymbol{\beta}-\sum_{i=1}^{r}a_{i}\bm{r}_{i})=\boldsymbol{0}$
and $\boldsymbol{\beta}-\sum_{i=1}^{r}a_{i}\bm{r}_{i}$ is thus in
$\mathcal{N}(\bm{X})$. Since $\bm{n}_{1},\bm{n}_{2},\cdots,\bm{n}_{k}$ is a
basis for the null space of $\bm{X}$,
$\boldsymbol{\beta}-\sum_{i=1}^{r}a_{i}\bm{r}_{i}$ can be expressed by a
combination of $\bm{n}_{1},\bm{n}_{2},\cdots,\bm{n}_{k}$:
$\boldsymbol{\beta}-\sum_{i=1}^{r}a_{i}\bm{r}_{i}=\sum_{j=1}^{k}b_{j}\bm{n}_{j}$,
i.e.,
$\boldsymbol{\beta}=\sum_{i=1}^{r}a_{i}\bm{r}_{i}+\sum_{j=1}^{k}b_{j}\bm{n}_{j}$.
That is, any vector $\boldsymbol{\beta}\in^{p}$ can be expressed by
$\\{\bm{r}_{1},\bm{r}_{2},\cdots,\bm{r}_{r},\bm{n}_{1},\bm{n}_{2},\cdots,\bm{n}_{k}\\}$
and the set forms a basis for p. Thus the dimension sum to $p$: $r+k=p$, i.e.,
$dim(\mathcal{N}(\bm{X}))+dim(\mathcal{C}(\bm{X}^{\top}))=p$. Similarly, we
can prove $dim(\mathcal{N}(\bm{X}^{\top}))+dim(\mathcal{C}(\bm{X}))=n$.

Figure 1 demonstrates two pairs of such orthogonal subspaces and shows how
$\bm{X}$ takes $\boldsymbol{\beta}$ into the column space. The dimensions of
the row space of $\bm{X}$ and the null space of $\bm{X}$ add to $p$. And the
dimensions of the column space of $\bm{X}$ and the null space of
$\bm{X}^{\top}$ add to $n$. The null space component goes to zero as
$\bm{X}\boldsymbol{\beta}_{\bm{n}}=\boldsymbol{0}\in^{n}$ which is the
intersection of the column space of $\bm{X}$ and the null space of
$\bm{X}^{\top}$. The row space component goes to column space as
$\bm{X}\boldsymbol{\beta}_{\bm{r}}=\bm{X}(\boldsymbol{\beta}_{\bm{r}}+\boldsymbol{\beta}_{\bm{n}})=\bm{y}\in\mathcal{C}(\bm{X})$.

##  3 SVD in the Fundamental Theorem of Linear Algebra

By QR decomposition, we factor matrix into an orthogonal matrix (see (Strang,
2009; Trefethen and Bau III, 1997; Strang, 2021; Lu, 2021a, b), and the
complexity and applications of QR decomposition). Instead of factoring matrix
into one orthogonal matrix, SVD gives rise to two orthogonal matrices. We
illustrate the result of SVD in the following theorem. And in Appendix E, we
provide a rigorous proof for the existence of SVD.

(a) Reduced SVD decomposition

(b) Full SVD decomposition

Figure 2: Comparison of reduced and full SVD. White entries are zero and blue
entries are not necessarily zero. In reduced SVD, we remove $n-r$ silent
columns from $\bm{U}$ and $p-r$ silent columns from $\bm{V}$.

######  Theorem 15 (Full SVD for Rectangular Matrices)

For every real $n\times p$ matrix $\bm{X}$ with rank $r$, then matrix $\bm{X}$
can be factored as

$\bm{X}=\bm{U}\boldsymbol{\Sigma}\bm{V}^{\top},$

where the left-upper side of $\boldsymbol{\Sigma}\in$n×p is a diagonal matrix,
that is
$\boldsymbol{\Sigma}=\begin{bmatrix}\boldsymbol{\Sigma}_{1}&\boldsymbol{0}\\\
\boldsymbol{0}&\boldsymbol{0}\end{bmatrix}$ where
$\boldsymbol{\Sigma}_{1}=diag(\sigma_{1},\sigma_{2}\cdots,\sigma_{r})\in^{r\times
r}$ with $\sigma_{1}\geq\sigma_{2}\geq\cdots\geq\sigma_{r}$ and

$\bullet$ $\sigma_{i}$’s are the nonzero singular values of matrix $\bm{X}$,
in the meantime, they are the (positive) square roots of the nonzero
eigenvalues of $\bm{X}^{\top}\bm{X}$ and $\bm{X}\bm{X}^{\top}$.

$\bullet$ $\bm{U}\in{\color[rgb]{0,0,1}{}^{n\times n}}$ contains the $r$
eigenvectors of $\bm{X}\bm{X}^{\top}$ corresponding to the $r$ nonzero
eigenvalues of $\bm{X}\bm{X}^{\top}$ and $n-r$ extra orthonormal vectors from
$\mathcal{N}(\bm{X}^{\top})$.

$\bullet$ $\bm{V}\in{\color[rgb]{0,0,1}{}^{p\times p}}$ contains the $r$
eigenvectors of $\bm{X}^{\top}\bm{X}$ corresponding to the $r$ nonzero
eigenvalues of $\bm{X}^{\top}\bm{X}$ and $p-r$ extra orthonormal vectors from
$\mathcal{N}(\bm{X})$.

$\bullet$ Moreover, the columns of $\bm{U}$ and $\bm{V}$ are called the left
and right singular vectors of $\bm{X}$, respectively.

$\bullet$ Further, the columns of $\bm{U}$ and $\bm{V}$ are orthonormal, and
$\bm{U}$ and $\bm{V}$ are orthogonal matrices.

In particular, we can write the matrix decomposition by
$\bm{X}=\bm{U}\boldsymbol{\Sigma}\bm{V}^{\top}=\sum_{i=1}^{r}\sigma_{i}\bm{u}_{i}\bm{v}_{i}^{\top}$,
which is a sum of $r$ rank-one matrices.

Figure 3: Second Figure: Orthonormal bases that diagonalize $\bm{X}$ from SVD.
$\\{\bm{v}_{1},\bm{v}_{2},\cdots,\bm{v}_{r}\\}$ is an orthonormal basis of
$\mathcal{C}(\bm{X}^{\top})$, and
$\\{\bm{u}_{1},\bm{u}_{2},\cdots,\bm{u}_{r}\\}$ is an orthonormal basis of
$\mathcal{C}(\bm{X})$. $\bm{X}$ transfers the row basis $\bm{v}_{i}$ into
column basis $\bm{u}_{i}$ by $\sigma_{i}\bm{u}_{i}=\bm{X}\bm{v}_{i}$ for all
$i\in\\{1,2,\cdots,r\\}$.

There is a version of reduced SVD (see Theorem 53 in Appendix E) by removing
the silent columns in $\bm{U}$ and $\bm{V}$. The comparison of reduced and
full SVD is shown in Figure 2 where white entries are zero and blue entries
are not necessarily zero.

The fundamental theorem of linear algebra tells us there exists a basis for
each subspace. Specifically, from SVD, we can find an orthonormal basis for
each subspace.

######  Lemma 16 (Four Orthonormal Basis in SVD)

Given the full SVD of matrix $\bm{X}=\bm{U}\boldsymbol{\Sigma}\bm{V}^{\top}$,
where $\bm{U}=[\bm{u}_{1},\bm{u}_{2},\cdots,\bm{u}_{n}]$ and
$\bm{V}=[\bm{v}_{1},\bm{v}_{2},\cdots,\bm{v}_{p}]$ are the column partitions
of $\bm{U}$ and $\bm{V}$. Then, we have the following property:

$\bullet$ $\\{\bm{v}_{1},\bm{v}_{2},\cdots,\bm{v}_{r}\\}$ is an orthonormal
basis of the row space, $\mathcal{C}(\bm{X}^{\top})$;

$\bullet$ $\\{\bm{v}_{r+1},\bm{v}_{r+2},\cdots,\bm{v}_{p}\\}$ is an
orthonormal basis of $\mathcal{N}(\bm{X})$;

$\bullet$ $\\{\bm{u}_{1},\bm{u}_{2},\cdots,\bm{u}_{r}\\}$ is an orthonormal
basis of the column space, $\mathcal{C}(\bm{X})$;

$\bullet$ $\\{\bm{u}_{r+1},\bm{u}_{r+2},\cdots,\bm{u}_{n}\\}$ is an
orthonormal basis of $\mathcal{N}(\bm{X}^{\top})$.

Proof [of Lemma 16] From Lemma 51, for symmetric matrix $\bm{X}^{\top}\bm{X}$,
$\mathcal{C}(\bm{X}^{\top}\bm{X})$ is spanned by the eigenvectors, thus
$\\{\bm{v}_{1},\bm{v}_{2}\cdots,\bm{v}_{r}\\}$ is an orthonormal basis of
$\mathcal{C}(\bm{X}^{\top}\bm{X})$.

Since,

1\. $\bm{X}^{\top}\bm{X}$ is symmetric, then the row space of
$\bm{X}^{\top}\bm{X}$ is equal to the column space of $\bm{X}^{\top}\bm{X}$.

2\. All rows of $\bm{X}^{\top}\bm{X}$ are combination of rows of $\bm{X}$, so
the row space of $\bm{X}^{\top}\bm{X}$ $\subseteq$ row space of $\bm{X}$,
i.e., $\mathcal{C}(\bm{X}^{\top}\bm{X})\subseteq\mathcal{C}(\bm{X}^{\top})$.

3\. Since $rank(\bm{X}^{\top}\bm{X})=rank(\bm{X})$ by Lemma 42, we then have

The row space of $\bm{X}^{\top}\bm{X}$ = the column space of
$\bm{X}^{\top}\bm{X}$ = the row space of $\bm{X}$, i.e.,
$\mathcal{C}(\bm{X}^{\top}\bm{X})=\mathcal{C}(\bm{X}^{\top})$. Thus
$\\{\bm{v}_{1},\bm{v}_{2},\cdots,\bm{v}_{r}\\}$ is an orthonormal basis of
$\mathcal{C}(\bm{X}^{\top})$.

Further, the space spanned by
$\\{\bm{v}_{r+1},\bm{v}_{r+2},\cdots,\bm{v}_{n}\\}$ is an orthogonal
complement to the space spanned by
$\\{\bm{v}_{1},\bm{v}_{2},\cdots,\bm{v}_{r}\\}$, so
$\\{\bm{v}_{r+1},\bm{v}_{r+2},\cdots,\bm{v}_{n}\\}$ is an orthonormal basis of
$\mathcal{N}(\bm{X})$.

If we apply this process to $\bm{X}\bm{X}^{\top}$, we will prove the rest
claims in the lemma. As an alternative way, we realize that
$\\{\bm{u}_{1},\bm{u}_{2},\cdots,\bm{u}_{r}\\}$ is a basis for the column
space of $\bm{X}$ by Lemma 13 222As a recap, for any matrix $\bm{X}$, let
$\\{\bm{r}_{1},\bm{r}_{2},\cdots,\bm{r}_{r}\\}$ be a set of vectors in p which
forms a basis for the row space, then
$\\{\bm{X}\bm{r}_{1},\bm{X}\bm{r}_{2},\cdots,\bm{X}\bm{r}_{r}\\}$ is a basis
for the column space of $\bm{X}$., since
$\bm{u}_{i}=\frac{\bm{X}\bm{v}_{i}}{\sigma_{i}},\,\forall
i\in\\{1,2,\cdots,r\\}$.

The relationship of the four subspaces is demonstrated in Figure 3 where
$\bm{X}$ transfers the row basis $\bm{v}_{i}$ into column basis $\bm{u}_{i}$
by $\sigma_{i}\bm{u}_{i}=\bm{X}\bm{v}_{i}$ for all $i\in\\{1,2,\cdots,r\\}$.

##  4 Least Squares in the Fundamental Theorem of Linear Algebra

Figure 4: Third Figure: Least Squares, row space to column space view.
$\hat{\boldsymbol{\beta}}$ minimizes $||\bm{y}-\bm{X}\boldsymbol{\beta}||^{2}$
such that $\hat{\boldsymbol{\beta}}$ is in the row space of $\bm{X}$.

Let’s consider the overdetermined system $\bm{y}=\bm{X}\boldsymbol{\beta}$,
where $\bm{X}\in^{n\times p}$ is the input data matrix, $\bm{y}\in^{n}$ is the
observation matrix (target matrix), and the sample number $n$ is larger than
the dimension number $p$. $\boldsymbol{\beta}$ is a vector of weights of the
linear model. Normally $\bm{X}$ will have full column rank since the data from
real world has large chance to be unrelated. The solution of least squares is
to make the error $\bm{y}-\bm{X}\boldsymbol{\beta}$ as small as possible with
respect to the mean squared error. $\bm{X}\boldsymbol{\beta}$ is a combination
of the columns of $\bm{X}$, as a result, $\bm{X}\boldsymbol{\beta}$ can never
leave the column space of $\bm{X}$ such that we should choose the closest
point to $\bm{y}$ in the column space (Strang, 1993; Lu, 2021b). This point is
the projection $\hat{\bm{y}}$ of $\bm{y}$ onto the column space of $\bm{X}$.
Then the error vector $\bm{e}=\bm{y}-\hat{\bm{y}}$ has minimal length. In
another word, the best combination
$\hat{\bm{y}}=\bm{X}\hat{\boldsymbol{\beta}}$ is the projection of $\bm{y}$
onto the column space. The error $\bm{e}$ is perpendicular to the column
space. Therefore $\bm{e}=\bm{y}-\bm{X}\hat{\boldsymbol{\beta}}$ is in the null
space of $\bm{X}^{\top}$:

$\bm{X}^{\top}(\bm{y}-\bm{X}\hat{\boldsymbol{\beta}})=\boldsymbol{0}\qquad\text{or}\qquad\bm{X}^{\top}\bm{y}=\bm{X}^{\top}\bm{X}\hat{\boldsymbol{\beta}},$

which is also known as the normal equation. The ordinary least squares (OLS)
estimator $\hat{\boldsymbol{\beta}}$ from this normal equation is
$\hat{\boldsymbol{\beta}}=(\bm{X}^{\top}\bm{X})^{-1}\bm{X}^{\top}\bm{y}$. The
relationship between $\bm{e}$ and $\hat{\bm{y}}$ is shown in Figure 4 where
$\bm{y}$ is split into $\hat{\bm{y}}+\bm{e}$. In addition, since the column
space of $\bm{X}$ and the null space of $\bm{X}^{\top}$ span the whole n
space, any vector $\bm{y}$ can be split into a vector $\hat{\bm{y}}$ in the
column space of $\bm{X}$ and a vector $\bm{e}$ in the null space of
$\bm{X}^{\top}$. Moreover, it can be shown that the OLS estimator
$\hat{\boldsymbol{\beta}}$ is in the row space of $\bm{X}$, i.e., it cannot be
split into a combination of two components that are in the row space of
$\bm{X}$ and the null space of $\bm{X}$ respectively (see
$\hat{\boldsymbol{\beta}}$ via the pseudo-inverse of $\bm{X}$ in Section 5,
$\hat{\boldsymbol{\beta}}$ is a linear combination of the orthonormal basis of
the row space).

To conclude, we avoid solving the equation $\bm{y}=\bm{X}\boldsymbol{\beta}$
by removing $\bm{e}$ from $\bm{y}$ and solve
$\hat{\bm{y}}=\bm{X}\hat{\boldsymbol{\beta}}$ instead:

$\bm{X}\boldsymbol{\beta}=\bm{y}=\hat{\bm{y}}+\bm{e}\,\,\mathrm{is\,impossible;}\qquad\bm{X}\hat{\boldsymbol{\beta}}=\hat{\bm{y}}\,\,\mathrm{is\,possible.}$

##  5 Least Squares via the Full SVD for Rank Deficient Matrices

In the previous section, we assume $\bm{X}$ has full rank. However, if
$\bm{X}$ does not have full column rank, $\bm{X}^{\top}\bm{X}$ is not
invertible. We thus can use SVD decomposition of $\bm{X}$ to solve the least
squares problem with rank-deficient $\bm{X}$. And we illustrate this rank-
deficient least squares method in the following theorem.

######  Theorem 17 (LS via SVD for Rank Deficient Matrix)

Let $\bm{X}\in^{n\times p}$, $\bm{X}=\bm{U}\boldsymbol{\Sigma}\bm{V}^{\top}$
is its full SVD decomposition with $\bm{U}\in^{n\times n}$ and
$\bm{V}\in^{p\times p}$ being orthogonal matrices and
$rank(\bm{X})=r\leq\min\\{n,p\\}$. Suppose
$\bm{U}=[\bm{u}_{1},\bm{u}_{2},\cdots,\bm{u}_{n}]$,
$\bm{V}=[\bm{v}_{1},\bm{v}_{2},\cdots,\bm{v}_{p}]$ and $\bm{y}\in^{n}$, then
the LS solution to $\bm{X}\boldsymbol{\beta}=\bm{y}$ is given by

$\hat{\boldsymbol{\beta}}=\sum_{i=1}^{r}\frac{\bm{u}_{i}^{\top}\bm{y}}{\sigma_{i}}\bm{v}_{i}=\bm{V}\boldsymbol{\Sigma}^{+}\bm{U}^{\top}\bm{y},$

where the upper-left side of $\boldsymbol{\Sigma}^{+}\in^{p\times n}$ is a
diagonal matrix
$diag(\frac{1}{\sigma_{1}},\frac{1}{\sigma_{2}},\cdots,\frac{1}{\sigma_{r}})$.

Proof [of Theorem 17] Write out the loss to be minimized

$\displaystyle||\bm{X}\boldsymbol{\beta}-\bm{y}||^{2}$
$\displaystyle=(\bm{X}\boldsymbol{\beta}-\bm{y})^{\top}(\bm{X}\boldsymbol{\beta}-\bm{y})$
$\displaystyle=(\bm{X}\boldsymbol{\beta}-\bm{y})^{\top}\bm{U}\bm{U}^{\top}(\bm{X}\boldsymbol{\beta}-\bm{y})\qquad$
$\displaystyle(\text{Since $\bm{U}$ is an orthogonal matrix})$
$\displaystyle=||\bm{U}^{\top}\bm{X}\boldsymbol{\beta}-\bm{U}^{\top}\bm{y}||^{2}\qquad$
$\displaystyle(\text{Invariant under orthogonal})$
$\displaystyle=||\bm{U}^{\top}\bm{X}\bm{V}\bm{V}^{\top}\boldsymbol{\beta}-\bm{U}^{\top}\bm{y}||^{2}\qquad$
$\displaystyle(\text{Since $\bm{V}$ is an orthogonal matrix})$
$\displaystyle=||\boldsymbol{\Sigma}\boldsymbol{\alpha}-\bm{U}^{\top}\bm{y}||^{2}\qquad$
$\displaystyle(\text{Let
$\boldsymbol{\alpha}=\bm{V}^{\top}\boldsymbol{\beta}$})$
$\displaystyle=\sum_{i=1}^{r}(\sigma_{i}\boldsymbol{\alpha}_{i}-\bm{u}_{i}^{\top}\bm{y})^{2}+\sum_{i=r+1}^{n}(\bm{u}_{i}^{\top}\bm{y})^{2}.\qquad$
$\displaystyle(\text{Since $\sigma_{r+1}=\sigma_{r+2}=\cdots=\sigma_{n}=0$})$

Since $\boldsymbol{\beta}$ only appears in $\boldsymbol{\alpha}$, we just need
to set $\boldsymbol{\alpha}_{i}=\frac{\bm{u}_{i}^{\top}\bm{y}}{\sigma_{i}}$
for all $i\in\\{1,2,\cdots,r\\}$ to minimize the above equation. For any value
of
$\boldsymbol{\alpha}_{r+1},\boldsymbol{\alpha}_{r+2},\cdots,\boldsymbol{\alpha}_{p}$,
it won’t change the result. From the regularization point of view we can set
them to be 0 (to get minimal length). This gives us the LS solution via SVD:

$\hat{\boldsymbol{\beta}}=\sum_{i=1}^{r}\frac{\bm{u}_{i}^{\top}\bm{y}}{\sigma_{i}}\bm{v}_{i}=\bm{V}\boldsymbol{\Sigma}^{+}\bm{U}^{\top}\bm{y}=\bm{X}^{+}\bm{y},$

where $\bm{X}^{+}=\bm{V}\boldsymbol{\Sigma}^{+}\bm{U}^{\top}\in^{p\times n}$
is known as the pseudo-inverse of $\bm{X}$. Please refer to Section 6 for a
detailed discussion about pseudo-inverse where we also prove that the column
space of $\bm{X}^{+}$ is equal to the row space of $\bm{X}$, and the row space
of $\bm{X}^{+}$ is equal to the column space of $\bm{X}$.

Figure 5: Fourth Figure: Least Squares, column space to row space view.
$\bm{X}^{+}$: Pseudo-inverse of $\bm{X}$.

######  Lemma 18 (LS in the Four Subspaces of Linear Algebra via SVD)

Assume $\bm{X}\in^{n\times p}$ is fixed and does not necessarily have full
rank with $n>p$. Consider the overdetermined system
$\bm{y}=\bm{X}\boldsymbol{\beta}$. Then, we can split $\bm{y}$ into
$\hat{\bm{y}}+\bm{e}$, where $\hat{\bm{y}}$ is in the column space of $\bm{X}$
and $\bm{e}$ is in the null space of $\bm{X}^{\top}$. We can always find this
split since the column space of $\bm{X}$ and the null space of $\bm{X}^{\top}$
span the whole space n. The relationship between $\bm{e}$ and $\bm{p}$ is
shown in Figure 5. Let $\bm{X}^{+}=\bm{V}\boldsymbol{\Sigma}^{+}\bm{U}^{\top}$
be the pseudo-inverse of $\bm{X}$. The pseudo-inverse $\bm{X}^{+}$ agrees with
$\bm{X}^{-1}$ when $\bm{X}$ is invertible. Then, we have the following
properties (also shown in Figure 5):

1\. For $\bm{e}\in\mathcal{N}(\bm{X}^{\top})$, it follows that
$\bm{X}^{+}\bm{e}=\boldsymbol{0}\in^{p}$.

2\. Given OLS solution $\hat{\boldsymbol{\beta}}$ via SVD, it follows that
$\bm{X}^{+}\hat{\bm{y}}=\bm{X}^{+}\bm{y}=\hat{\boldsymbol{\beta}}$.

3\. OLS solution $\hat{\boldsymbol{\beta}}$ is in the row space of $\bm{X}$,
i.e., it cannot be split into a combination of two components that are in row
space of $\bm{X}$ and null space of $\bm{X}$ respectively. This is the reason
why $\hat{\boldsymbol{\beta}}$ in Figure 5 is in the row space of $\bm{X}$
rather than in p in general.

Proof [of Lemma 18] Since $\bm{e}$ is in $\mathcal{N}(\bm{X}^{\top})$ and
perpendicular to $\mathcal{C}(\bm{X})$, and we have shown in Lemma 16,
$\\{\bm{u}_{1},\bm{u}_{2},\cdots,\bm{u}_{r}\\}$ is an orthonormal basis of
$\mathcal{C}(\bm{X})$, then the first $r$ components of $\bm{U}^{\top}\bm{e}$
are all zeros. Therefore,
$\bm{X}^{+}\bm{e}=\bm{V}\boldsymbol{\Sigma}^{+}\bm{U}^{\top}\bm{e}=\boldsymbol{0}$
(see Figure 5 where we transform $\bm{e}$ from $\mathcal{N}(\bm{X}^{\top})$
into the $\boldsymbol{0}\in^{p}$ by $\bm{X}^{+}$). Moreover,
$\hat{\boldsymbol{\beta}}=\bm{X}^{+}\bm{y}=\bm{X}^{+}(\hat{\bm{y}}+\bm{e})=\bm{X}^{+}\hat{\bm{y}}$.

Further, we have also shown in Lemma 16 that
$\\{\bm{v}_{1},\bm{v}_{2},\cdots,\bm{v}_{r}\\}$ is an orthonormal basis of
$\mathcal{C}(\bm{X}^{\top})$,
$\hat{\boldsymbol{\beta}}=\sum_{i=1}^{r}\frac{\bm{u}_{i}^{\top}\bm{y}}{\sigma_{i}}\bm{v}_{i}$
thus is in the row space of $\bm{X}$.
Actually, from projection point of view, the $\hat{\bm{y}}$ is the closest
point to $\bm{y}$ in the column space of $\bm{X}$. This point is the
projection $\hat{\bm{y}}$ of $\bm{y}$. Then the error vector
$\bm{e}=\bm{y}-\hat{\bm{y}}$ has minimal length (Lu, 2021b).

Apart from this LS solution from SVD, in practice, a direct solution of the
normal equations can lead to numerical difficulties when $\bm{X}^{\top}\bm{X}$
is close to singular. In particular, when two or more of the columns in
$\bm{X}^{\top}\bm{X}$ are co-linear, the resulting parameter values can have
large magnitude. Such near degeneracies will not be uncommon when dealing with
real data sets. The resulting numerical difficulties can be addressed using
the SVD as well (Bishop, 2006).

##  6 Pseudo-Inverse in the Fundamental Theorem of Linear Algebra

If the matrix $\bm{X}$ is nonsingular, then the linear system
$\bm{y}=\bm{X}\boldsymbol{\beta}$ can be easily solved by the inverse of
$\bm{X}$ such that $\hat{\boldsymbol{\beta}}=\bm{X}^{-1}\bm{y}$. However, the
inverse of an $n\times p$ matrix $\bm{X}$ does not exist if $\bm{X}$ is not
square or $\bm{X}$ is singular. But we can still find its pseudo-inverse, a
$p\times n$ matrix denoted by $\bm{X}^{+}$. Before the discussion of pseudo-
inverse, we firstly introduce one-sided inverse, generalized inverse, and
reflexive generalized inverse that are prerequisites of pseudo-inverse and
some the properties of them.

###  6.1 One-sided Inverse

######  Definition 19 (One-sided Inverse)

For any matrix $\bm{X}\in^{n\times p}$, if there is a matrix $\bm{X}_{L}^{-1}$
such that

$\bm{X}_{L}^{-1}\bm{X}=\bm{I}_{p},$

then $\bm{X}_{L}^{-1}$ is a left inverse of $\bm{X}$, and $\bm{X}$ is called
left-invertible. Similarly, if there is a matrix $\bm{X}_{R}^{-1}$ such that

$\bm{X}\bm{X}_{R}^{-1}=\bm{I}_{n},$

then $\bm{X}_{R}^{-1}$ is a right inverse of $\bm{X}$, and $\bm{X}$ is called
right-invertible.

A word on the notation: Note here the superscript $-1$ in $\bm{X}_{L}^{-1}$
and $\bm{X}_{R}^{-1}$ does not mean the inverse of $\bm{X}_{L}$ or
$\bm{X}_{R}$ but the one-sided inverse of $\bm{X}$.

######  Lemma 20 (One-sided Invertible)

For any matrix $\bm{X}\in^{n\times p}$, we have

$\bullet$ $\bm{X}$ is left-invertible if and only if $\bm{X}$ has full column
rank (which implies $n\geq p$);

$\bullet$ $\bm{X}$ is right-invertible if and only if $\bm{X}$ has full row
rank (which implies $n\leq p$).

Proof [of Lemma 20] Suppose $\bm{X}$ has full column rank, then
$\bm{X}^{\top}\bm{X}\in^{p\times p}$ has full rank (see Lemma 42). Therefore,
$(\bm{X}^{\top}\bm{X})^{-1}(\bm{X}^{\top}\bm{X})=\bm{I}_{p}$. That is
$(\bm{X}^{\top}\bm{X})^{-1}\bm{X}^{\top}$ is a left inverse of $\bm{X}$.

For the reverse, now suppose $\bm{X}$ is left-invertible such that
$\bm{X}_{L}^{-1}\bm{X}=\bm{I}_{p}$. Since all rows of $\bm{X}_{L}^{-1}\bm{X}$
are the combinations of the rows of $\bm{X}$, that is, the row space of
$\bm{X}_{L}^{-1}\bm{X}$ is a subset of the row space of $\bm{X}$. We then have
$rank(\bm{X})\geq rank(\bm{X}_{L}^{-1}\bm{X})=rank(\bm{I}_{p})=p$ which
implies $rank(\bm{X})=p$ and $\bm{X}$ has full column rank.

Similarly, we can show $\bm{X}$ is right-invertible if and only if $\bm{X}$
has full row rank and $\bm{X}^{\top}(\bm{X}\bm{X}^{\top})^{-1}$ is a right
inverse of $\bm{X}$.

We have shown in the above proof that
$(\bm{X}^{\top}\bm{X})^{-1}\bm{X}^{\top}$ is a specific left inverse of
$\bm{X}$ if $\bm{X}$ has full column rank, and
$\bm{X}^{\top}(\bm{X}\bm{X}^{\top})^{-1}$ is a specific right inverse of
$\bm{X}$ if $\bm{X}$ has full row rank. However, the inverse of a $p\times p$
nonsingular matrix requires $2p^{3}$ floating points operations (flops) which
is a complex procedure (Lu, 2021a). In our case, the inverse of
$\bm{X}^{\top}\bm{X}$ requires $2p^{3}$ flops and the inverse of
$\bm{X}\bm{X}^{\top}$ requires $2n^{3}$ flops. A simpler way to find a one-
sided inverse is through elementary operations.

Suppose $\bm{X}\in^{n\times p}$ has full column rank and we apply row
elementary operations $\bm{E}\in^{n\times n}$ on $[\bm{X},\bm{I}_{n}]$ such
that

$\bm{E}\begin{bmatrix}\bm{X}&\bm{I}_{n}\end{bmatrix}=\begin{bmatrix}\bm{I}_{p}&\bm{G}\\\
\boldsymbol{0}&\bm{Z}\end{bmatrix},$ (1)

where $\bm{G}\in^{p\times n}$, $\bm{I}_{n}$ is an $n\times n$ identity matrix,
$\bm{I}_{p}$ is a $p\times p$ identity matrix, and $\bm{Z}$ is an $(n-p)\times
n$ matrix. Then, it can be easily verified that $\bm{G}\bm{X}=\bm{I}_{p}$ and
$\bm{G}$ is a left inverse of $\bm{X}$.

Similarly, suppose $\bm{X}\in^{n\times p}$ has full row rank and we apply
column elementary operations $\bm{E}\in^{p\times p}$ on
$[\bm{X}^{\top},\bm{I}_{p}]^{\top}$ such that

$\begin{bmatrix}\bm{X}\\\
\bm{I}_{p}\end{bmatrix}\bm{E}=\begin{bmatrix}\bm{I}_{n}&\boldsymbol{0}\\\
\bm{G}&\bm{Z}\end{bmatrix},$ (2)

where $\bm{Z}$ is a $p\times(p-n)$ matrix. Then, $\bm{G}\in^{p\times n}$ is a
right inverse of $\bm{X}$.

More generally, the following two propositions show us how to find more left
inverses or right inverses of a matrix.

######  Proposition 21 (Finding Left Inverse)

Suppose $\bm{X}\in^{n\times p}$ is left-invertible ($n\geq p$), then

$\bm{X}_{L}^{-1}=\begin{bmatrix}(\bm{X}_{1}^{-1}-\bm{Y}\bm{X}_{2}\bm{X}_{1}^{-1})&\bm{Y}\end{bmatrix}\bm{E},$

is a left inverse of $\bm{X}$, where $\bm{Y}\in^{p\times(n-p)}$ can be any
matrix, and $\bm{E}\bm{X}=\begin{bmatrix}\bm{X}_{1}\\\
\bm{X}_{2}\end{bmatrix}$ is the row elementary transformation of $\bm{X}$ such
that $\bm{X}_{1}\in^{p\times p}$ is invertible (since $\bm{X}$ has full column
rank $p$) and $\bm{E}\in^{n\times n}$.

We can verify that $\bm{G}$ in Equation 1 is a specific left inverse of
$\bm{X}$ by setting $\bm{Y}=\boldsymbol{0}$. Since
$\bm{E}=\begin{bmatrix}\bm{G}\\\ *\end{bmatrix}$, $\bm{X}_{1}=\bm{I}_{p}$, and
$\bm{X}_{2}=\boldsymbol{0}$, we have

$\bm{X}_{L}^{-1}=\begin{bmatrix}(\bm{X}_{1}^{-1}-\bm{Y}\bm{X}_{2}\bm{X}_{1}^{-1})&\bm{Y}\end{bmatrix}\bm{E}=\bm{G}+\bm{Y}\bm{Z}=\bm{G},$

where the last equation is from the assumption that $\bm{Y}=\boldsymbol{0}$.

######  Proposition 22 (Finding Right Inverse)

Suppose $\bm{X}\in^{n\times p}$ is right-invertible ($n\leq p$), then

$\bm{X}_{R}^{-1}=\bm{E}\begin{bmatrix}(\bm{X}_{1}^{-1}-\bm{X}_{1}^{-1}\bm{X}_{2}\bm{Y})\\\
\bm{Y}\end{bmatrix},$

is a right inverse of $\bm{X}$, where $\bm{Y}\in^{(p-n)\times n}$ can be any
matrix, and $\bm{X}\bm{E}=\begin{bmatrix}\bm{X}_{1}&\bm{X}_{2}\end{bmatrix}$
is the column elementary transformation of $\bm{X}$ such that
$\bm{X}_{1}\in^{n\times n}$ is invertible (since $\bm{X}$ has full row rank
$n$) and $\bm{E}\in^{p\times p}$.

Similarly, we can verify that $\bm{G}$ in Equation 2 is a specific right
inverse of $\bm{X}$ by setting $\bm{Y}=\boldsymbol{0}$. Since
$\bm{E}=[\bm{G},\bm{Z}]$, $\bm{X}_{1}=\bm{I}_{n}$, and
$\bm{X}_{2}=\boldsymbol{0}$, we have

$\bm{X}_{R}^{-1}=\bm{E}\begin{bmatrix}(\bm{X}_{1}^{-1}-\bm{X}_{1}^{-1}\bm{X}_{2}\bm{Y})\\\
\bm{Y}\end{bmatrix}=\bm{G}+\bm{Z}\bm{Y}=\bm{G},$

where again the last equality is from the assumption that
$\bm{Y}=\boldsymbol{0}$.

Figure 6: Fifth Figure: $\bm{X}$ is left-invertible, the row space of $\bm{X}$
is the whole space of p.
$(\bm{I}_{n}-\bm{X}\bm{X}_{L}^{-1})\bm{y}=\boldsymbol{0}$ implies $\bm{y}$ is
in the column space of $\bm{X}$ such that the solution of
$\bm{X}\boldsymbol{\beta}=\bm{y}$ is unique.

Under specific condition, the linear system $\bm{X}\boldsymbol{\beta}=\bm{y}$
has an unique solution.

######  Proposition 23 (Unique Linear System Solution)

Suppose $\bm{X}\in^{n\times p}$ is left-invertible ($n\geq p$), and
$\bm{X}_{L}^{-1}$ is the left inverse of $\bm{X}$. Then the linear system
$\bm{X}\boldsymbol{\beta}=\bm{y}$ has an unique solution if and only if

$(\bm{I}_{n}-\bm{X}\bm{X}_{L}^{-1})\bm{y}=\boldsymbol{0}.$

And the unique solution is given by

$\hat{\boldsymbol{\beta}}=(\bm{X}^{\top}\bm{X})^{-1}\bm{X}^{\top}\bm{y}.$

Proof [of Proposition 23] Suppose $\boldsymbol{\beta}_{0}$ is the solution of
$\bm{X}\boldsymbol{\beta}=\bm{y}$, then

$\displaystyle\bm{X}\bm{X}_{L}^{-1}(\bm{X}\boldsymbol{\beta}_{0})$
$\displaystyle=\bm{X}\bm{X}_{L}^{-1}\bm{y}$
$\displaystyle\bm{X}(\bm{X}_{L}^{-1}\bm{X})\boldsymbol{\beta}_{0}$
$\displaystyle=\bm{X}\boldsymbol{\beta}_{0}=\bm{y}.$

That is, $\bm{X}\bm{X}_{L}^{-1}\bm{y}=\bm{y}$ and
$(\bm{I}_{n}-\bm{X}\bm{X}_{L}^{-1})\bm{y}=\boldsymbol{0}$. For the reverse,
suppose $(\bm{I}_{n}-\bm{X}\bm{X}_{L}^{-1})\bm{y}=\boldsymbol{0}$, and let
$\boldsymbol{\beta}_{0}=\bm{X}_{L}^{-1}\bm{y}$. Then substitute
$\boldsymbol{\beta}_{0}=\bm{X}_{L}^{-1}\bm{y}$ into
$(\bm{I}_{n}-\bm{X}\bm{X}_{L}^{-1})\bm{y}=\boldsymbol{0}$, we have

$\bm{X}\boldsymbol{\beta}_{0}=\bm{y},$

which implies $\boldsymbol{\beta}_{0}=\bm{X}_{L}^{-1}\bm{y}$ is a solution of
$\bm{X}\boldsymbol{\beta}=\bm{y}$ if
$(\bm{I}_{n}-\bm{X}\bm{X}_{L}^{-1})\bm{y}=\boldsymbol{0}$.

To prove the uniqueness, suppose $\boldsymbol{\beta}_{0}$ and
$\boldsymbol{\beta}_{1}$ are two solutions of
$\bm{X}\boldsymbol{\beta}=\bm{y}$. We have
$\bm{X}\boldsymbol{\beta}_{0}=\bm{X}\boldsymbol{\beta}_{1}=\bm{y}$ such that
$\bm{X}(\boldsymbol{\beta}_{0}-\boldsymbol{\beta}_{1})=\boldsymbol{0}$. Since
$\bm{X}$ is left-invertible so that $\bm{X}$ has full column rank $p$, the
dimension of the row space of $\bm{X}$ is $p$ as well such that the null space
of $\bm{X}$ is of dimension 0 (i.e.,
$\dim(\mathcal{C}(\bm{X}^{\top}))+\dim(\mathcal{N}(\bm{X}))=p$ by fundamental
theorem of linear algebra, see Theorem 14). Then
$\boldsymbol{\beta}_{0}=\boldsymbol{\beta}_{1}$ which completes the proof.

In the fundamental theorem of linear algebra Figure 1, the row space of
$\bm{X}$ is the whole space of p if $\bm{X}$ is left-invertible (i.e.,
$\bm{X}$ has full column rank $p$). If the condition
$(\bm{I}_{n}-\bm{X}\bm{X}_{L}^{-1})\bm{y}=\boldsymbol{0}$ is satisfied, it
implies that $\bm{y}$ is in the column space of $\bm{X}$ such that
$\bm{X}\boldsymbol{\beta}=\bm{y}$ has at least one solution and the above
proposition shows that this solution is unique. The situation is shown in
Figure 6.

Figure 7: Sixth Figure: $\bm{X}$ is right-invertible, the column space of
$\bm{X}$ is the whole space of n.

######  Proposition 24 (Always Have Solution)

Suppose $\bm{X}\in^{n\times p}$ is right-invertible (which implies $n\leq p$),
and $\bm{X}_{R}^{-1}$ is a right inverse of $\bm{X}$. Then for any
$\bm{y}\in^{n}$, the linear system $\bm{X}\boldsymbol{\beta}=\bm{y}$ has
solutions, and the solution is given by

$\hat{\boldsymbol{\beta}}=\bm{X}_{R}^{-1}\bm{y},$

where $\bm{X}_{R}^{-1}$ is a right inverse of $\bm{X}$ and the right inverse
is not necessarily unique.

Proof [of Proposition 24] It can be easily verified that

$(\bm{X}\bm{X}_{R}^{-1})\bm{y}=\bm{I}_{n}\bm{y}=\bm{y},$

so that $\bm{X}_{R}^{-1}\bm{y}$ is a solution of
$\bm{X}\boldsymbol{\beta}=\bm{y}$.

We notice that if $\bm{X}$ is right-invertible, then $\bm{X}$ has full row
rank $n$. In the fundamental theorem of linear algebra Figure 1, the column
space of $\bm{X}$ is the whole space of n if $\bm{X}$ is right-invertible.
Then any vector $\bm{y}\in^{n}$ is in the column space of $\bm{X}$ such that
$\bm{X}\boldsymbol{\beta}=\bm{y}$ has at least one solution. The situation is
shown in Figure 7. This implies $p\geq n$. When $p>n$, we can always find some
$\boldsymbol{\beta}_{n}\in\mathcal{N}(\bm{X})$ such that the solution of
$\bm{X}\boldsymbol{\beta}=\bm{y}$ is not unique. When $p=n$, the solution is
apparently unique and the right inverse degenerates to the inverse.

###  6.2 Generalized Inverse (g-inverse)

We mentioned previously that if matrix $\bm{X}$ is nonsingular, then the
linear system $\bm{y}=\bm{X}\boldsymbol{\beta}$ can be easily solved by the
inverse of $\bm{X}$ such that $\hat{\boldsymbol{\beta}}=\bm{X}^{-1}\bm{y}$.
However, the inverse of an $n\times p$ matrix $\bm{X}$ does not exist if
$\bm{X}$ is not square or $\bm{X}$ is singular. But still, when $\bm{y}$ is in
the column space of $\bm{X}$, we can find the solution of the linear system as
well. The relationship between the solution $\hat{\boldsymbol{\beta}}$ and
$\bm{y}$ is given by the generalized inverse of $\bm{X}$:
$\hat{\boldsymbol{\beta}}=\bm{X}^{-}\bm{y}$.

######  Definition 25 (Generalized Inverse)

Any matrix $\bm{X}\in^{n\times p}$ has rank $r$ with $r\leq p\leq n$. Then a
generalized inverse $\bm{X}^{-}\in^{p\times n}$ of $\bm{X}$ is a matrix that
satisfies

$(C1)\qquad\bm{X}\bm{X}^{-}\bm{X}=\bm{X},$

or equivalently,

$(C1.1)\qquad\bm{X}\bm{X}^{-}\bm{y}=\bm{y}$

for any $\bm{y}\in\mathcal{C}(\bm{X})$.

To see the equivalence between $(C1)$ and $(C1.1)$, that is, we want to show
$\bm{X}$ satisfies $(C1)$ if and only if it satisfies $(C1.1)$. For any
$\bm{y}\in\mathcal{C}(\bm{X})$, we can find a $\boldsymbol{\beta}\in^{p}$ such
that $\bm{X}\boldsymbol{\beta}=\bm{y}$. If $\bm{X}$ and $\bm{X}^{-}$ satisfy
$(C1)$, then

$\bm{X}\bm{X}^{-}\bm{X}\boldsymbol{\beta}=\bm{X}\boldsymbol{\beta}\qquad\underrightarrow{\text{leads
to}}\qquad\bm{X}\bm{X}^{-}\bm{y}=\bm{y},$

which implies $\bm{X}$ and $\bm{X}^{-}$ also satisfy $(C1.1)$. For the
reverse, suppose $\bm{X}$ and $\bm{X}^{-}$ satisfy $(C1.1)$, then

$\bm{X}\bm{X}^{-}\bm{y}=\bm{y}\qquad\underrightarrow{\text{leads
to}}\qquad\bm{X}\bm{X}^{-}\bm{X}\boldsymbol{\beta}=\bm{X}\boldsymbol{\beta},$

which implies $\bm{X}$ and $\bm{X}^{-}$ also satisfy $(C1)$.

Multiply on the left of $(C1)$ by $\bm{X}^{-}$ and follow the definition of
projection matrix,333A projection matrix is a matrix that is idempotent. And
an orthogonal projection matrix is a matrix that is both symmetric and
idempotent. See (Lu, 2021b). we obtain
$\bm{X}^{-}\bm{X}\bm{X}^{-}\bm{X}=\bm{X}^{-}\bm{X}$ such that
$\bm{X}^{-}\bm{X}$ is idempotent, which implies $\bm{X}^{-}\bm{X}$ is a
projection matrix (not necessarily to be an orthogonal projection).

######  Lemma 26 (Projection Matrix from Generalized Inverse)

For any matrix $\bm{X}$, and its generalized inverse $\bm{X}^{-}$,
$\bm{X}^{-}\bm{X}$ is a projection matrix but not necessarily an orthogonal
projection. Same claim can be applied to $\bm{X}\bm{X}^{-}$ as well.

######  Lemma 27 (Rank of Generalized Inverse)

For any matrix $\bm{X}\in^{n\times p}$, and its generalized inverse
$\bm{X}^{-}\in^{p\times n}$, then

$rank(\bm{X}^{-})\geq rank(\bm{X}).$

Specifically, we also have
$rank(\bm{X})=rank(\bm{X}\bm{X}^{-})=rank(\bm{X}^{-}\bm{X})$.

Proof [of Lemma 27] From $(C1)$, we notice that
$rank(\bm{X})=rank(\bm{X}\bm{X}^{-}\bm{X})$. And

$rank(\bm{X}\bm{X}^{-}\bm{X})\leq rank(\bm{X}\bm{X}^{-})\leq
rank(\bm{X}^{-}),$

where the first inequality comes from the fact that the columns of
$\bm{X}\bm{X}^{-}\bm{X}$ are combinations of columns of $\bm{X}\bm{X}^{-}$,
and the second inequality comes from the fact that the rows of
$\bm{X}\bm{X}^{-}$ are combinations of rows of $\bm{X}^{-}$.

For the second part, we have

$rank(\bm{X})\geq rank(\bm{X}\bm{X}^{-})\geq rank(\bm{X}\bm{X}^{-}\bm{X}),$

where the first inequality is from the fact that the columns of
$\bm{X}\bm{X}^{-}$are combinations of the columns of $\bm{X}$, and the second
inequality is from the fact that the columns of $\bm{X}\bm{X}^{-}\bm{X}$ are
combinations of the columns of $\bm{X}\bm{X}^{-}$. From $(C1)$ again,
$rank(\bm{X})=rank(\bm{X}\bm{X}^{-}\bm{X})$ which implies by ”sandwiching”
that

$rank(\bm{X})=rank(\bm{X}\bm{X}^{-})=rank(\bm{X}\bm{X}^{-}\bm{X}).$

Similarly, we also have

$rank(\bm{X})\geq rank(\bm{X}^{-}\bm{X})\geq rank(\bm{X}\bm{X}^{-}\bm{X}),$

where the first inequality is from the fact that the rows of
$\bm{X}^{-}\bm{X}$ are combinations of the rows of $\bm{X}$, and the second
inequality is from the fact that the rows of $\bm{X}\bm{X}^{-}\bm{X}$ are
combinations of the rows of $\bm{X}^{-}\bm{X}$. By ”sandwiching” again, we
have

$rank(\bm{X})=rank(\bm{X}^{-}\bm{X})=rank(\bm{X}\bm{X}^{-}\bm{X}),$

which completes the proof.

In Lemma 20, we have shown that the left inverse exists if and only if
$\bm{X}$ has full column rank, and the right inverse exists if and only if
$\bm{X}$ has full row rank. However, this is not required in generalized
inverse. When this full rank condition is satisfied, we have another property
as follows.

######  Lemma 28 (Full Rank Generalized Inverse)

For any matrix $\bm{X}\in^{n\times p}$, and its generalized inverse
$\bm{X}^{-}\in^{p\times n}$, then we have

1). $\bm{X}$ has full column rank if and only if
$\bm{X}^{-}\bm{X}=\bm{I}_{p}$;

2). $\bm{X}$ has full row rank if and only if $\bm{X}\bm{X}^{-}=\bm{I}_{n}$.

Proof [of Lemma 28] For 1). Suppose $\bm{X}$ has full column rank, and we have
shown in Lemma 27 that
$rank(\bm{X})=rank(\bm{X}\bm{X}^{-})=rank(\bm{X}^{-}\bm{X})$. Then
$rank(\bm{X}^{-}\bm{X})=rank(\bm{X})=p$ and $\bm{X}^{-}\bm{X}\in^{p\times p}$
is nonsingular. We have

$\bm{I}_{p}=(\bm{X}^{-}\bm{X})(\bm{X}^{-}\bm{X})^{-1}=\bm{X}^{-}(\bm{X}\bm{X}^{-}\bm{X})(\bm{X}^{-}\bm{X})^{-1}=\bm{X}^{-}\bm{X}.$

For the reverse, suppose $\bm{X}^{-}\bm{X}=\bm{I}_{p}$ which implies
$rank(\bm{X}^{-}\bm{X})=p$. From $rank(\bm{X}^{-}\bm{X})=rank(\bm{X})$, we
have $rank(\bm{X})=p$ such that $\bm{X}$ has full column rank.

Similarly, we can show $\bm{X}$ has full row rank if and only if
$\bm{X}\bm{X}^{-}=\bm{I}_{n}$.

######  Lemma 29 (Constructing Generalized Inverse)

For any matrix $\bm{X}\in^{n\times p}$, and its generalized inverse
$\bm{X}^{-}\in^{p\times n}$, then there exists a $p\times n$ matrix $\bm{A}$
such that

$\bar{\bm{X}}=\bm{X}^{-}+\bm{A}-\bm{X}^{-}\bm{X}\bm{A}\bm{X}\bm{X}^{-}$ (3)

is also a generalized inverse of $\bm{X}$. In addition, for any generalized
inverse $\bar{\bm{X}}$, there exists a matrix $\bm{A}$ so that Equation 3 is
satisfied.

Proof [of Lemma 29] Write out the equation

$\displaystyle\bm{X}\bar{\bm{X}}\bm{X}$
$\displaystyle=\bm{X}(\bm{X}^{-}+\bm{A}-\bm{X}^{-}\bm{X}\bm{A}\bm{X}\bm{X}^{-})\bm{X}=\bm{X}\bm{X}^{-}\bm{X}+\bm{X}\bm{A}\bm{X}-(\bm{X}\bm{X}^{-}\bm{X})\bm{A}(\bm{X}\bm{X}^{-}\bm{X})$
$\displaystyle=\bm{X}\bm{X}^{-}\bm{X}+\bm{X}\bm{A}\bm{X}-\bm{X}\bm{A}\bm{X}=\bm{X},$

so that $\bar{\bm{X}}$ is a generalized inverse of $\bm{X}$.

Suppose now that $\bm{B}$ is any generalized inverse of $\bm{X}$, and define
$\bm{A}=\bm{B}-\bm{X}^{-}$. Recall that $\bm{X}\bm{B}\bm{X}=\bm{X}$, we have

$\displaystyle\bm{X}^{-}+\bm{A}-\bm{X}^{-}\bm{X}\bm{A}\bm{X}\bm{X}^{-}$
$\displaystyle=\bm{X}^{-}+(\bm{B}-\bm{X}^{-})-\bm{X}^{-}\bm{X}(\bm{B}-\bm{X}^{-})\bm{X}\bm{X}^{-}$
$\displaystyle=\bm{B}-\bm{X}^{-}(\bm{X}\bm{B}\bm{X})\bm{X}^{-}+\bm{X}^{-}(\bm{X}\bm{X}^{-}\bm{X})\bm{X}^{-}$
$\displaystyle=\bm{B}-\bm{X}^{-}\bm{X}\bm{X}^{-}+\bm{X}^{-}\bm{X}\bm{X}^{-}$
$\displaystyle=\bm{B},$

which implies $\bm{A}$ can be constructed for any generalized inverse
$\bm{B}$.

######  Lemma 30 (Generalized Inverse Properties)

For any matrix $\bm{X}\in^{n\times p}$, and its generalized inverse
$\bm{X}^{-}\in^{p\times n}$, then

1). $(\bm{X}^{\top})^{-}=(\bm{X}^{-})^{\top}$, i.e., $(\bm{X}^{-})^{\top}$ is
the generalized inverse of $\bm{X}^{\top}$;

2). For any $a\neq 0$, $\frac{1}{a}\bm{X}^{-}$ is the generalized inverse of
$a\bm{X}$;

3). Suppose $\bm{A}\in^{n\times n}$ and $\bm{B}\in^{p\times p}$ are both
invertible, then $\bm{B}^{-1}\bm{X}^{-}\bm{A}^{-1}$ is a generalized inverse
of $\bm{A}\bm{X}\bm{B}$;

4). $\mathcal{C}(\bm{X}\bm{X}^{-})=\mathcal{C}(\bm{X})$ and
$\mathcal{N}(\bm{X}^{-}\bm{X})=\mathcal{N}(\bm{X})$.

Proof [of Lemma 30] For 1), from $(C1)$, $\bm{X}\bm{X}^{-}\bm{X}=\bm{X}$, we
have $\bm{X}^{\top}(\bm{X}^{-})^{\top}\bm{X}^{\top}=\bm{X}^{\top}$ such that
$(\bm{X}^{-})^{\top}$ is the generalized inverse of $\bm{X}^{\top}$.

For 2), it can be easily verified that
$(a\bm{X})(\frac{1}{a}\bm{X}^{-})(a\bm{X})=(a\bm{X})$ such that
$\frac{1}{a}\bm{X}^{-}$ is the generalized inverse of $a\bm{X}$ for any $a\neq
0$.

For 3), we realize that
$(\bm{A}\bm{X}\bm{B})(\bm{B}^{-1}\bm{X}^{-}\bm{A}^{-1})(\bm{A}\bm{X}\bm{B})=\bm{A}\bm{X}\bm{X}^{-}\bm{X}\bm{B}=\bm{A}\bm{X}\bm{B}$
which implies $\bm{B}^{-1}\bm{X}^{-}\bm{A}^{-1}$ is a generalized inverse of
$\bm{A}\bm{X}\bm{B}$.

For 4), since the columns of $\bm{X}\bm{X}^{-}$ are the combinations of the
columns of $\bm{X}$, then
$\mathcal{C}(\bm{X}\bm{X}^{-})\subseteq\mathcal{C}(\bm{X})$. And we proved
that $rank(\bm{X})=rank(\bm{X}\bm{X}^{-})$ in Lemma 27, then
$\mathcal{C}(\bm{X}\bm{X}^{-})=\mathcal{C}(\bm{X})$. Similarly, we could prove
$\mathcal{N}(\bm{X}^{-}\bm{X})=\mathcal{N}(\bm{X})$.

###  6.3 Reflexive Generalized Inverse (rg-inverse)

Figure 8: Relationship of different inverses.

######  Definition 31 (Reflexive Generalized Inverse)

Any matrix $\bm{X}\in^{n\times p}$ has rank $r$ with $r\leq\min\\{p,n\\}$.
Then a reflexive generalized inverse $\bm{X}_{r}^{-}\in^{p\times n}$ of
$\bm{X}$ is a matrix that satisfies

$(C1)\qquad\bm{X}\bm{X}_{r}^{-}\bm{X}=\bm{X},$

and

$(C2)\qquad\bm{X}_{r}^{-}\bm{X}\bm{X}_{r}^{-}=\bm{X}_{r}^{-}.$

That is $\bm{X}_{r}^{-}$ is a g-inverse of $\bm{X}$, and $\bm{X}$ is a
g-inverse of $\bm{X}_{r}^{-}$.

Let $\bm{X}$ be of rank $r$, it can be factored as
$\bm{X}=\bm{E}_{1}\begin{bmatrix}\bm{I}_{r}&\boldsymbol{0}\\\
\boldsymbol{0}&\boldsymbol{0}\end{bmatrix}\bm{E}_{2}$, where
$\bm{E}_{1}\in^{n\times n}$, $\bm{E}_{2}\in^{p\times p}$ are elementary
transformations on $\bm{X}$. Then, we can construct such a reflexive
generalized inverse of $\bm{X}$ as

$\bm{X}_{r}^{-}=\bm{E}_{2}^{-1}\begin{bmatrix}\bm{I}_{r}&\bm{A}\\\
\bm{B}&\bm{B}\bm{A}\end{bmatrix}\bm{E}_{1}^{-1},$

where $\bm{A}\in^{r\times(n-r)}$, $\bm{B}\in^{(p-r)\times r}$ can be any
matrix so that the reflexive generalized inverse is not unique. This
construction of the reflexive generalized inverse also shows that reflexive
generalized inverse exists for any matrix. This implies reflexive generalized
inverse is a more general inverse of $\bm{X}$ compared to the one-sided
inverse which may not exist.

######  Lemma 32 (Reflexive Generalized Inverse from G-Inverse)

For any matrix $\bm{X}\in^{n\times p}$, and $\bm{A}$, $\bm{B}$ are two
generalized inverses of $\bm{X}$, then

$\bm{Z}=\bm{A}\bm{X}\bm{B}$

is a reflexive generalized inverse of $\bm{X}$.

It can be easily verified that $\bm{X}\bm{Z}\bm{X}=\bm{X}$ and
$\bm{Z}\bm{X}\bm{Z}=\bm{Z}$.

######  Lemma 33 (Reflexive Generalized Inverse from G-Inverse)

For any matrix $\bm{X}\in^{n\times p}$, then the following two matrices
$\bm{A}$ and $\bm{B}$ are two reflexive generalized inverses of $\bm{X}$:

$\displaystyle\bm{A}$ $\displaystyle=(\bm{X}^{\top}\bm{X})^{-}\bm{X}^{\top},$
$\displaystyle\bm{B}$ $\displaystyle=\bm{X}^{\top}(\bm{X}\bm{X}^{\top})^{-},$

where $(\bm{X}^{\top}\bm{X})^{-}$ is a g-inverse of $(\bm{X}^{\top}\bm{X})$,
and $(\bm{X}\bm{X}^{\top})^{-}$ is a g-inverse of $(\bm{X}\bm{X}^{\top})$.

Proof [of Lemma 33] Let’s first check the following result.  Since the columns
of $\bm{X}^{\top}\bm{X}$ are combinations of the columns of $\bm{X}^{\top}$,
we have $\mathcal{C}(\bm{X}^{\top}\bm{X})\subseteq\mathcal{C}(\bm{X}^{\top})$.
In Lemma 42, we proved that, $rank(\bm{X}^{\top}\bm{X})=rank(\bm{X})$. This
implies $rank(\bm{X}^{\top}\bm{X})=rank(\bm{X}^{\top})$ and
$\mathcal{C}(\bm{X}^{\top}\bm{X})=\mathcal{C}(\bm{X}^{\top})$. Furthermore,
the orthogonal complement of $\mathcal{C}(\bm{X}^{\top})$ is
$\mathcal{N}(\bm{X})$, and the orthogonal complement of
$\mathcal{C}(\bm{X}^{\top}\bm{X})$ is $\mathcal{N}(\bm{X}^{\top}\bm{X})$.
Therefore, by fundamental theorem of linear algebra in Appendix 2.2, we have
$\mathcal{C}(\bm{X}^{\top}\bm{X})=\mathcal{C}(\bm{X}^{\top}),\qquad\mathcal{N}(\bm{X}^{\top}\bm{X})=\mathcal{N}(\bm{X}).$
Then there exists a set of vectors
$\bm{z}_{1},\bm{z}_{2},\cdots,\bm{z}_{n}\in^{p}$ such that column-$i$ of
$\bm{X}^{\top}$ can be expressed as $\bm{X}^{\top}\bm{X}\bm{z}_{i}$. That is,
for $\bm{Z}=[\bm{z}_{1},\bm{z}_{2},\cdots,\bm{z}_{n}]$, we have

$\bm{X}^{\top}=\bm{X}^{\top}\bm{X}\bm{Z}.$

Then,

$\bm{X}\bm{A}\bm{X}=(\bm{X}^{\top}\bm{X}\bm{Z})^{\top}(\bm{X}^{\top}\bm{X})^{-}\bm{X}^{\top}\bm{X}=\bm{Z}^{\top}\bm{X}^{\top}\bm{X}(\bm{X}^{\top}\bm{X})^{-}\bm{X}^{\top}\bm{X}.$

By condition $(C1.1)$ of g-inverse, we have
$\bm{X}^{\top}\bm{X}(\bm{X}^{\top}\bm{X})^{-}\bm{y}=\bm{y}$ for any $\bm{y}$.
This implies
$\bm{X}^{\top}\bm{X}(\bm{X}^{\top}\bm{X})^{-}\bm{X}^{\top}\bm{X}=\bm{X}^{\top}\bm{X}$
and

$\bm{X}\bm{A}\bm{X}=(\bm{X}^{\top}\bm{X}\bm{Z})^{\top}(\bm{X}^{\top}\bm{X})^{-}\bm{X}^{\top}\bm{X}=\bm{Z}^{\top}\bm{X}^{\top}\bm{X}=\bm{X}.$
(4)

Write out $\bm{A}\bm{X}\bm{A}$, we have

$\bm{A}\bm{X}\bm{A}=(\bm{X}^{\top}\bm{X})^{-}\bm{X}^{\top}\bm{X}(\bm{X}^{\top}\bm{X})^{-}\bm{X}^{\top}.$

Same argument can be applied to
$\bm{X}^{\top}\bm{X}(\bm{X}^{\top}\bm{X})^{-}\bm{X}^{\top}=\bm{X}^{\top}$.
Then,

$\bm{A}\bm{X}\bm{A}=(\bm{X}^{\top}\bm{X})^{-}\bm{X}^{\top}=\bm{A}.$ (5)

Combine Equation 4 and Equation 5, we conclude that $\bm{A}$ is a reflexive
generalized inverse of $\bm{X}$. Similarly, we can show $\bm{B}$ is a
reflexive generalized inverse of $\bm{X}$ as well.

From the definition, we realize that reflexive generalized inverse is a
special generalized inverse. Under specific condition, the two inverses are
equivalent.

######  Lemma 34 (Reflexive Generalized Inverse in G-Inverse)

For any matrix $\bm{X}\in^{n\times p}$, and $\bm{X}^{-}\in^{p\times n}$ is a
generalized inverse of $\bm{X}$, then $\bm{X}^{-}$ is a reflexive generalized
inverse of $\bm{X}$ if and only if $rank(\bm{X})=rank(\bm{X}^{-})$.

Proof [of Lemma 34] Suppose $\bm{X}^{-}$ is a generalized inverse of $\bm{X}$,
then $\bm{X}\bm{X}^{-}\bm{X}=\bm{X}$. Suppose further, $\bm{X}^{-}$ is also a
reflexive generalized inverse, then $\bm{X}^{-}\bm{X}\bm{X}^{-}=\bm{X}^{-}$.
We have

$\displaystyle rank(\bm{X})$ $\displaystyle=rank(\bm{X}\bm{X}^{-}\bm{X})\leq
rank(\bm{X}^{-})=rank(\bm{X}^{-}\bm{X}\bm{X}^{-})\leq rank(\bm{X})$

where the two inequalities are from Lemma 27. This implies
$rank(\bm{X})=rank(\bm{X}^{-})$.

For the reverse, suppose $\bm{X}^{-}$ is a generalized inverse of $\bm{X}$,
then $\bm{X}\bm{X}^{-}\bm{X}=\bm{X}$. And suppose further
$rank(\bm{X})=rank(\bm{X}^{-})$, we have

$rank(\bm{X})=rank(\bm{X}\bm{X}^{-}\bm{X})\leq rank(\bm{X}^{-}\bm{X})\leq
rank(\bm{X}^{-})=rank(\bm{X}),$

where the first inequality is from that fact that the rows of
$\bm{X}\bm{X}^{-}\bm{X}$ are combinations of the rows of $\bm{X}^{-}\bm{X}$,
and the second inequality is from the fact that the columns of
$\bm{X}^{-}\bm{X}$ are combinations of the columns of $\bm{X}^{-}$. This
implies $rank(\bm{X}^{-}\bm{X})=rank(\bm{X}^{-})$ and
$\mathcal{C}(\bm{X}^{-}\bm{X})=\mathcal{C}(\bm{X}^{-})$. Then there exists a
set of vectors
$\boldsymbol{\alpha}_{1},\boldsymbol{\alpha}_{2},\cdots,\boldsymbol{\alpha}_{n}\in^{p}$
such that column-$i$ of $\bm{X}^{-}$ can be expressed as
$\bm{X}^{-}\bm{X}\boldsymbol{\alpha}_{i}$. That is, for
$\bm{A}=[\boldsymbol{\alpha}_{1},\boldsymbol{\alpha}_{2},\cdots,\boldsymbol{\alpha}_{n}]$,
we have

$\bm{X}^{-}=\bm{X}^{-}\bm{X}\bm{A}.$

We realize again that $\bm{X}=\bm{X}\bm{X}^{-}\bm{X}$, then

$\bm{X}=\bm{X}\bm{X}^{-}\bm{X}=\bm{X}(\bm{X}^{-}\bm{X}\bm{A})\bm{X}=\bm{X}\bm{A}\bm{X},$

where the last equality is form condition $(C1.1)$ and $\bm{A}$ is a
generalized inverse of $\bm{X}$. From Lemma 32,
$\bm{X}^{-}=\bm{X}^{-}\bm{X}\bm{A}$ is a reflexive generalized inverse of
$\bm{X}$ which completes the proof.

######  Proposition 35 (Rank of Reflexive Generalized Inverse)

For any matrix $\bm{X}\in^{n\times p}$, and its generalized inverse
$\bm{X}_{r}^{-}\in^{p\times n}$. Combine the result in Lemma 34 and the result
from the rank of g-inverses in Lemma 27, we have
$rank(\bm{X}_{r}^{-})=rank(\bm{X})=rank(\bm{X}\bm{X}_{r}^{-})=rank(\bm{X}_{r}^{-}\bm{X}).$

######  Lemma 36 (Reflexive Generalized Inverse Properties)

For any matrix $\bm{X}\in^{n\times p}$, and its reflexive generalized inverse
$\bm{X}_{r}^{-}\in^{p\times n}$, then

1\. $\mathcal{C}(\bm{X}\bm{X}_{r}^{-})=\mathcal{C}(\bm{X})$ and
$\mathcal{N}(\bm{X}_{r}^{-}\bm{X})=\mathcal{N}(\bm{X})$.

2\. $\mathcal{C}(\bm{X}_{r}^{-}\bm{X})=\mathcal{C}(\bm{X}_{r}^{-})$ and
$\mathcal{N}(\bm{X}\bm{X}_{r}^{-})=\mathcal{N}(\bm{X}_{r}^{-})$.

Proof [of Lemma 36] Suppose $\bm{X}^{-}$ is a g-inverse of $\bm{X}$, we proved
in Lemma 30 that $\mathcal{C}(\bm{X}\bm{X}^{-})=\mathcal{C}(\bm{X})$ and
$\mathcal{N}(\bm{X}^{-}\bm{X})=\mathcal{N}(\bm{X})$. Since $\bm{X}^{-}_{r}$ is
a g-inverse of $\bm{X}$, and $\bm{X}$ is a g-inverse of $\bm{X}^{-}_{r}$, we
complete the proof.

###  6.4 Pseudo-Inverse

As we mentioned previously, for a matrix $\bm{X}\in^{n\times p}$, we can find
its pseudo-inverse, a $p\times n$ matrix denoted by $\bm{X}^{+}$. In words,
when $\bm{X}$ multiplies a vector $\boldsymbol{\beta}$ in its row space, this
produces $\bm{X}\boldsymbol{\beta}$ in the column space (see Figure 1). Those
two spaces have equal dimension $r$, i.e., the rank. $\bm{X}$ is always
invertible when restricted to these spaces and $\bm{X}^{+}$ inverts $\bm{X}$.
That is, $\bm{X}^{+}\bm{X}\boldsymbol{\beta}=\boldsymbol{\beta}$ when
$\boldsymbol{\beta}$ is in the row space of $\bm{X}$. And
$\bm{X}\bm{X}^{+}\bm{y}=\bm{y}$ when $\bm{y}$ is in the column space of
$\bm{X}$ (see Figure 9).

The null space of $\bm{X}^{+}$ is the null space of $\bm{X}^{\top}$. It
contains the vectors $\bm{y}$ in n with $\bm{X}^{\top}\bm{y}=\boldsymbol{0}$.
Those vectors $\bm{y}$ are perpendicular to every $\bm{X}\boldsymbol{\beta}$
in the column space. We delay the proof of this property in Lemma 39.

More formally, the pseudo-inverse, or also known as Moore-Penrose pseudo-
inverse, $\bm{X}^{+}$, is defined by the unique $p\times n$ matrix satisfying
the following four criteria

$\boxed{\begin{aligned}
&(C1)\qquad\bm{X}\bm{X}^{+}\bm{X}&=&\bm{X}\qquad&(\bm{X}^{+}\text{ is a
g-inverse of }\bm{X})\\\
&(C2)\qquad\bm{X}^{+}\bm{X}\bm{X}^{+}&=&\bm{X}^{+}\qquad&(\bm{X}\text{ is a
g-inverse of }\bm{X}^{+})\\\
&(C3)\qquad(\bm{X}\bm{X}^{+})^{\top}&=&\bm{X}\bm{X}^{+}\\\
&(C4)\qquad(\bm{X}^{+}\bm{X})^{\top}&=&\bm{X}^{+}\bm{X}\end{aligned}}$ (6)

In Lemma 26, we claimed that $\bm{X}\bm{X}^{+}$ and $\bm{X}^{+}\bm{X}$ are
idempotent if $\bm{X}^{+}$ is a g-inverse of $\bm{X}$, and thus they are both
projection matrix. For $\bm{X}^{+}$ to be pseudo-inverse, by $(C3),(C4)$
conditions, they are symmetric such that they are orthogonal projection as
well (again, please refer to (Lu, 2021b) for more details about orthogonal
projection matrices).

From the pseudo-inverse of the matrix from CR decomposition, we can also claim
that any matrix has a pseudo-inverse.

######  Lemma 37 (Existence of Pseudo-Inverse)

Every matrix $\bm{X}$ has a pseudo-inverse.

Proof [of Lemma 37] For the CR decomposition of $\bm{X}=\bm{C}\bm{R}$. 444CR
decomposition: Any rank-$r$ matrix $\bm{A}\in^{n\times p}$ can be factored as
$\bm{A}=\bm{C}\bm{R}$, where $\bm{C}$ is some $r$ independent columns of
$\bm{A}$, and $\bm{R}$ is a $r\times p$ matrix to reconstruct the columns of
$\bm{A}$ from columns of $\bm{C}$. In particular, $\bm{R}$ is the row reduced
echelon form of $\bm{A}$ without the zero rows, and both $\bm{C}$ and $\bm{R}$
have full rank $r$. Let

$\bm{X}^{+}=\bm{R}^{+}\bm{C}^{+}=\bm{R}^{\top}(\bm{R}\bm{R}^{\top})^{-1}(\bm{C}^{\top}\bm{C})^{-1}\bm{C}^{\top},$

where $\bm{R}^{+}=\bm{R}^{\top}(\bm{R}\bm{R}^{\top})^{-1}$ and
$\bm{C}^{+}=(\bm{C}^{\top}\bm{C})^{-1}\bm{C}^{\top}$. 555It can be easily
checked that $\bm{R}^{+}$ is the pseudo-inverse of $\bm{R}$ and $\bm{C}^{+}$
is the pseudo-inverse of $\bm{C}$. $\bm{R}\bm{R}^{\top}$ and
$\bm{C}^{\top}\bm{C}$ are invertible since $\bm{C}\in^{n\times r}$ and
$\bm{R}\in^{r\times p}$ have full rank $r$ from the property of CR
decomposition.

Then, we can check that

$\displaystyle(C1)\qquad\bm{X}\bm{X}^{+}\bm{X}$ $\displaystyle=$
$\displaystyle\bm{C}\bm{R}\left(\bm{R}^{\top}(\bm{R}\bm{R}^{\top})^{-1}(\bm{C}^{\top}\bm{C})^{-1}\bm{C}^{\top}\right)\bm{C}\bm{R}=\bm{C}\bm{R}=\bm{X},$
$\displaystyle(C2)\qquad\bm{X}^{+}\bm{X}\bm{X}^{+}$ $\displaystyle=$
$\displaystyle\left(\bm{R}^{\top}(\bm{R}\bm{R}^{\top})^{-1}(\bm{C}^{\top}\bm{C})^{-1}\bm{C}^{\top}\right)\bm{C}\bm{R}\left(\bm{R}^{\top}(\bm{R}\bm{R}^{\top})^{-1}(\bm{C}^{\top}\bm{C})^{-1}\bm{C}^{\top}\right)$
$\displaystyle=$
$\displaystyle\bm{R}^{\top}(\bm{R}\bm{R}^{\top})^{-1}(\bm{C}^{\top}\bm{C})^{-1}\bm{C}^{\top}=\bm{X}^{+},$
$\displaystyle(C3)\qquad(\bm{X}\bm{X}^{+})^{\top}$ $\displaystyle=$
$\displaystyle\bm{C}(\bm{C}^{\top}\bm{C})^{-1}(\bm{R}\bm{R}^{\top})^{-1}\bm{R}\bm{R}^{\top}\bm{C}^{\top}=\bm{C}(\bm{C}^{\top}\bm{C})^{-1}\bm{C}^{\top}$
$\displaystyle=$
$\displaystyle\bm{C}\bm{R}\bm{R}^{\top}(\bm{R}\bm{R}^{\top})^{-1}(\bm{C}^{\top}\bm{C})^{-1}\bm{C}^{\top}=\bm{X}\bm{X}^{+},$
$\displaystyle(C4)\qquad(\bm{X}^{+}\bm{X})^{\top}$ $\displaystyle=$
$\displaystyle\bm{R}^{\top}\bm{C}^{\top}\bm{C}(\bm{C}^{\top}\bm{C})^{-1}(\bm{R}\bm{R}^{\top})^{-1}\bm{R}=\bm{R}^{\top}(\bm{R}\bm{R}^{\top})^{-1}\bm{R}$
$\displaystyle=$
$\displaystyle\bm{R}^{\top}(\bm{R}\bm{R}^{\top})^{-1}(\bm{C}^{\top}\bm{C})^{-1}\bm{C}^{\top}\bm{C}\bm{R}=\bm{X}^{+}\bm{X}.$

This implies $\bm{X}^{+}$ is the pseudo-inverse of $\bm{X}$ and the existence
of the pseudo-inverse.

######  Lemma 38 (Uniqueness of Pseudo-Inverse)

Every matrix $\bm{X}$ has a unique pseudo-inverse.

Proof [of Lemma 38] Suppose $\bm{X}_{1}^{+}$ and $\bm{X}_{2}^{+}$ are two
pseudo-inverses of $\bm{X}$. Then

$\displaystyle\bm{X}_{1}^{+}$
$\displaystyle=\bm{X}_{1}^{+}\bm{X}\bm{X}_{1}^{+}=\bm{X}_{1}^{+}(\bm{X}\bm{X}_{2}^{+}\bm{X})\bm{X}_{1}^{+}=\bm{X}_{1}^{+}(\bm{X}\bm{X}_{2}^{+})(\bm{X}\bm{X}_{1}^{+})\qquad$
$\displaystyle(\text{by $(C2),(C1)$})$
$\displaystyle=\bm{X}_{1}^{+}(\bm{X}\bm{X}_{2}^{+})^{\top}(\bm{X}\bm{X}_{1}^{+})^{\top}=\bm{X}_{1}^{+}\bm{X}_{2}^{+\top}\bm{X}^{\top}\bm{X}_{1}^{+\top}\bm{X}^{\top}\qquad$
$\displaystyle(\text{by $(C3)$})$
$\displaystyle=\bm{X}_{1}^{+}\bm{X}_{2}^{+\top}(\bm{X}\bm{X}_{1}^{+}\bm{X})^{\top}=\bm{X}_{1}^{+}\bm{X}_{2}^{+\top}\bm{X}^{\top}\qquad$
$\displaystyle(\text{by $(C1)$})$
$\displaystyle=\bm{X}_{1}^{+}(\bm{X}\bm{X}_{2}^{+})^{\top}=\bm{X}_{1}^{+}\bm{X}\bm{X}_{2}^{+}=\bm{X}_{1}^{+}(\bm{X}\bm{X}_{2}^{+}\bm{X})\bm{X}_{2}^{+}\qquad$
$\displaystyle(\text{by $(C3),(C1)$})$
$\displaystyle=(\bm{X}_{1}^{+}\bm{X})(\bm{X}_{2}^{+}\bm{X})\bm{X}_{2}^{+}=(\bm{X}_{1}^{+}\bm{X})^{\top}(\bm{X}_{2}^{+}\bm{X})^{\top}\bm{X}_{2}^{+}\qquad$
$\displaystyle(\text{by $(C4)$})$
$\displaystyle=(\bm{X}\bm{X}_{1}^{+}\bm{X})^{\top}\bm{X}_{2}^{+\top}\bm{X}_{2}^{+}=\bm{X}^{\top}\bm{X}_{2}^{+\top}\bm{X}_{2}^{+}\qquad$
$\displaystyle(\text{by $(C1)$})$
$\displaystyle=(\bm{X}_{2}^{+}\bm{X})^{\top}\bm{X}_{2}^{+}=\bm{X}_{2}^{+}\bm{X}\bm{X}_{2}^{+}=\bm{X}_{2}^{+},\qquad$
$\displaystyle(\text{by $(C4),(C2)$})$

which implies the uniqueness of pseudo-inverse.

Figure 9: Seventh Figure: Column space and row space of pseudo-inverse
$\bm{X}^{+}$. $\bm{X}$ transfers from row space to column space. $\bm{X}^{+}$
transfers from column space to row space. The split of $\bm{y}$ into
$\hat{\bm{y}}+\bm{e}$ and the transformation to $\boldsymbol{\beta}^{+}$ are
discussed in Section 6.5. This is a more detailed picture of the pseudo-
inverse compared to Figure 5.

We are now ready to show the four subspaces in pseudo-inverse.

######  Lemma 39 (Four Subspaces in Pseudo-Inverse)

For the pseudo-inverse $\bm{X}^{+}$ of $\bm{X}$, we have the following
properties:

$\bullet$ The column space of $\bm{X}^{+}$ is the same as the row space of
$\bm{X}$;

$\bullet$ The row space of $\bm{X}^{+}$ is the same as the column space of
$\bm{X}$;

$\bullet$ The null space of $\bm{X}^{+}$ is the same as the null space of
$\bm{X}^{\top}$;

$\bullet$ The null space of $\bm{X}^{+\top}$ is the same as the null space of
$\bm{X}$.

The relationship of the four subspaces is shown in Figure 9.

Proof [of Lemma 39] Since $\bm{X}^{+}$ is a special rg-inverse, by Lemma 36,
we have

$\displaystyle\mathcal{C}(\bm{X}\bm{X}^{+})$
$\displaystyle=\mathcal{C}(\bm{X})\qquad\text{and}\qquad\mathcal{N}(\bm{X}^{+}\bm{X})=\mathcal{N}(\bm{X})$
$\displaystyle\mathcal{C}(\bm{X}^{+}\bm{X})$
$\displaystyle=\mathcal{C}(\bm{X}^{+})\qquad\text{and}\qquad\mathcal{N}(\bm{X}\bm{X}^{+})=\mathcal{N}(\bm{X}^{+}).$

By $(C3)$ and $(C4)$ of the definition of pseudo-inverse, we also have

$(\bm{X}^{+}\bm{X})^{\top}=\bm{X}^{+}\bm{X}\qquad\text{and}\qquad(\bm{X}\bm{X}^{+})^{\top}=\bm{X}\bm{X}^{+}.$

By fundamental theorem of linear algebra, we realize that
$\mathcal{C}(\bm{X}\bm{X}^{+})$ is the orthogonal complement to
$\mathcal{N}((\bm{X}\bm{X}^{+})^{\top})$, and $\mathcal{C}(\bm{X}^{+}\bm{X})$
is the orthogonal complement to $\mathcal{N}((\bm{X}^{+}\bm{X})^{\top})$:

$\displaystyle\mathcal{C}(\bm{X}\bm{X}^{+})\perp\mathcal{N}((\bm{X}\bm{X}^{+})^{\top})$
$\displaystyle\qquad\underrightarrow{\text{leads
to}}\qquad\mathcal{C}(\bm{X}\bm{X}^{+})\perp\mathcal{N}(\bm{X}\bm{X}^{+})$
$\displaystyle\mathcal{C}(\bm{X}^{+}\bm{X})\perp\mathcal{N}((\bm{X}^{+}\bm{X})^{\top})$
$\displaystyle\qquad\underrightarrow{\text{leads
to}}\qquad\mathcal{C}(\bm{X}^{+}\bm{X})\perp\mathcal{N}(\bm{X}^{+}\bm{X}).$

This implies

$\displaystyle\mathcal{C}(\bm{X})\perp\mathcal{N}(\bm{X}^{+})\qquad\text{and}\qquad\mathcal{C}(\bm{X}^{+})\perp\mathcal{N}(\bm{X}).$

That is, $\mathcal{N}(\bm{X}^{+})=\mathcal{N}(\bm{X}^{\top})$ and
$\mathcal{C}(\bm{X}^{+})=\mathcal{C}(\bm{X}^{\top})$. By fundamental theorem
of linear algebra, this also implies
$\mathcal{C}(\bm{X}^{+\top})=\mathcal{C}(\bm{X})$ and
$\mathcal{N}(\bm{X}^{+\top})=\mathcal{N}(\bm{X})$.

To conclude, we compare the properties for different inverses of $\bm{X}$ in
Table 1.

| g-inverse | rg-inverse | pseudo-inverse
---|---|---|---
subspaces |  | $\mathcal{C}(\bm{X}\bm{X}^{-})=\mathcal{C}(\bm{X})$
---
$\mathcal{N}(\bm{X}^{-}\bm{X})=\mathcal{N}(\bm{X})$
| $\mathcal{C}(\bm{X}\bm{X}_{r}^{-})=\mathcal{C}(\bm{X})$
---
$\mathcal{N}(\bm{X}_{r}^{-}\bm{X})=\mathcal{N}(\bm{X})$
$\mathcal{C}(\bm{X}_{r}^{-}\bm{X})=\mathcal{C}(\bm{X}_{r}^{-})$
$\mathcal{N}(\bm{X}\bm{X}_{r}^{-})=\mathcal{N}(\bm{X}_{r}^{-})$
|
$\mathcal{C}(\bm{X}\bm{X}^{+})=\mathcal{C}(\bm{X})=\mathcal{C}(\bm{X}^{+\top})$
---
$\mathcal{N}(\bm{X}^{+}\bm{X})=\mathcal{N}(\bm{X})=\mathcal{N}(\bm{X}^{+\top})$
$\mathcal{C}(\bm{X}^{+}\bm{X})=\mathcal{C}(\bm{X}^{+})=\mathcal{C}(\bm{X}^{\top})$
$\mathcal{N}(\bm{X}\bm{X}^{+})=\mathcal{N}(\bm{X}^{+})=\mathcal{N}(\bm{X}^{\top})$
rank |  | $rank(\bm{X}\bm{X}^{-})$
---
$=rank(\bm{X}^{-}\bm{X})$
$=rank(\bm{X})$
$\leq rank(\bm{X}^{-})$
| $rank(\bm{X}_{r}^{-})$
---
$=rank(\bm{X})$
$=rank(\bm{X}\bm{X}_{r}^{-})$
$=rank(\bm{X}_{r}^{-}\bm{X})$
| $rank(\bm{X}^{+})$
---
$=rank(\bm{X})$
$=rank(\bm{X}\bm{X}^{+})$
$=rank(\bm{X}^{+}\bm{X})$
Table 1: Comparison of different inverses

######  Lemma 40 (Projection onto Column Space and Row Space)

For any matrix $\bm{X}\in^{n\times p}$ and its pseudo-inverse
$\bm{X}^{+}\in^{p\times n}$, $\bm{H}=\bm{X}\bm{X}^{+}$ is the orthogonal
projection onto column space of $\bm{X}$. Similarly, $\bm{P}=\bm{X}^{+}\bm{X}$
is the orthogonal projection onto row space of $\bm{X}$.

Proof [of Lemma 40] As
$\bm{H}^{\top}=(\bm{X}\bm{X}^{+})^{\top}=\bm{X}\bm{X}^{+}=\bm{H}$ from the
definition of the pseudo-inverse, and $\bm{H}$ is idempotent such that
$\bm{H}$ is an orthogonal projection. From Table 1, we conclude that
$\mathcal{C}(\bm{H})=\mathcal{C}(\bm{X}\bm{X}^{+})=\mathcal{C}(\bm{X})$. This
implies $\bm{H}$ is the orthogonal projection onto the column space of
$\bm{X}$. Similarly, we can prove $\bm{P}=\bm{X}^{+}\bm{X}$ is the orthogonal
projection onto row space of $\bm{X}$.

Specifically, we define in either of the following ways: $\bullet$ Case
$n>p=r$, i.e., matrix $\bm{X}$ has independent columns: $\bm{X}^{\top}\bm{X}$
is a $p\times p$ invertible matrix, and we define the left-pseudo-inverse:
$\boxed{\text{left-pseudo-
inverse}=\bm{X}^{+}=(\bm{X}^{\top}\bm{X})^{-1}\bm{X}^{\top}},$ which satisfies
$\bm{X}^{+}\bm{X}=(\bm{X}^{\top}\bm{X})^{-1}\bm{X}^{\top}\bm{X}=\bm{I}_{p}.$
But
$\bm{X}\bm{X}^{+}=\bm{X}(\bm{X}^{\top}\bm{X})^{-1}\bm{X}^{\top}\neq\bm{I}.$
$\bullet$ Case $p>n=r$, i.e., matrix $\bm{X}$ has independent rows:
$\bm{X}\bm{X}^{\top}$ is an $n\times n$ invertible matrix, and we define the
right-pseudo-inverse: $\boxed{\text{right-pseudo-
inverse}=\bm{X}^{+}=\bm{X}^{\top}(\bm{X}\bm{X}^{\top})^{-1}},$ which satisfies
$\bm{X}\bm{X}^{+}=\bm{X}\bm{X}^{\top}(\bm{X}\bm{X}^{\top})^{-1}=\bm{I}_{n}.$
But
$\bm{X}^{+}\bm{X}=\bm{X}^{\top}(\bm{X}\bm{X}^{\top})^{-1}\bm{X}\neq\bm{I}.$
(7) $\bullet$ Case rank-deficient: we delay the pseudo-inverse for rank-
deficient matrices in the next section. We can also show that
$(\bm{X}^{+})^{+}=\bm{X}$. If $n>p=r$, we have $\displaystyle(\bm{X}^{+})^{+}$
$\displaystyle=[(\bm{X}^{\top}\bm{X})^{-1}\bm{X}^{\top}]^{+}$
$\displaystyle=\bm{X}^{+\top}(\bm{X}^{+}\bm{X}^{+\top})^{-1}$
$\displaystyle(n>p=r)$
$\displaystyle=\left[(\bm{X}^{\top}\bm{X})^{-1}\bm{X}^{\top}\right]^{\top}\left\\{\left[(\bm{X}^{\top}\bm{X})^{-1}\bm{X}^{\top}\right]\left[(\bm{X}^{\top}\bm{X})^{-1}\bm{X}^{\top}\right]^{\top}\right\\}^{-1}$
$\displaystyle=\bm{X}(\bm{X}^{\top}\bm{X})^{-1}\left\\{(\bm{X}^{\top}\bm{X})^{-1}\bm{X}^{\top}\bm{X}(\bm{X}^{\top}\bm{X})^{-1}\right\\}^{-1}$
$\displaystyle=\bm{X}.$ Similarly, we can show $(\bm{X}^{+})^{+}=\bm{X}$ if
$p>n=r$. In particular, when $n=p$, $\bm{X}$ is square invertible matrix, then
both left and right-pseudo-inverse are the inverse of $\bm{X}$: left-pseudo-
inverse
$\displaystyle=\bm{X}^{+}=(\bm{X}^{\top}\bm{X})^{-1}\bm{X}^{\top}=\bm{X}^{-1}\bm{X}^{-\top}\bm{X}^{\top}=\bm{X}^{-1},$
right-pseudo-inverse
$\displaystyle=\bm{X}^{+}=\bm{X}^{\top}(\bm{X}\bm{X}^{\top})^{-1}=\bm{X}^{\top}\bm{X}^{-\top}\bm{X}^{-1}=\bm{X}^{-1}.$

###  6.5 Pseudo-Inverse in SVD

For full SVD of matrix $\bm{X}=\bm{U}\boldsymbol{\Sigma}\bm{V}^{\top}$.
Consider the following cases: $\bullet$ Case $n>p=r$: left-pseudo-inverse
$\displaystyle=\bm{X}^{+}=(\bm{X}^{\top}\bm{X})^{-1}\bm{X}^{\top}$
$\displaystyle=(\bm{V}\boldsymbol{\Sigma}^{\top}\bm{U}^{\top}\bm{U}\boldsymbol{\Sigma}\bm{V}^{\top})^{-1}\bm{V}\boldsymbol{\Sigma}^{\top}\bm{U}^{\top}$
$\displaystyle=\bm{V}(\boldsymbol{\Sigma}^{\top}\boldsymbol{\Sigma})^{-1}\bm{V}^{\top}\bm{V}\boldsymbol{\Sigma}^{\top}\bm{U}^{\top}$
$\displaystyle=\bm{V}[(\boldsymbol{\Sigma}^{\top}\boldsymbol{\Sigma})^{-1}\boldsymbol{\Sigma}^{\top}]\bm{U}^{\top}$
$\displaystyle=\bm{V}\boldsymbol{\Sigma}^{+}\bm{U}^{\top}.\qquad$
$\displaystyle(\boldsymbol{\Sigma}^{+}=(\boldsymbol{\Sigma}^{\top}\boldsymbol{\Sigma})^{-1}\boldsymbol{\Sigma}^{\top})$
$\bullet$ Case $p>n=r$: right-pseudo-inverse
$\displaystyle=\bm{X}^{+}=\bm{X}^{\top}(\bm{X}\bm{X}^{\top})^{-1}$
$\displaystyle=(\bm{U}\boldsymbol{\Sigma}\bm{V}^{\top})^{\top}[(\bm{U}\boldsymbol{\Sigma}\bm{V}^{\top})(\bm{U}\boldsymbol{\Sigma}\bm{V}^{\top})^{\top}]^{-1}$
$\displaystyle=\bm{V}\boldsymbol{\Sigma}^{\top}\bm{U}^{\top}(\bm{U}\boldsymbol{\Sigma}\bm{V}^{\top}\bm{V}\boldsymbol{\Sigma}^{\top}\bm{U}^{\top})^{-1}$
$\displaystyle=\bm{V}\boldsymbol{\Sigma}^{\top}\bm{U}^{\top}\bm{U}^{-\top}(\boldsymbol{\Sigma}\boldsymbol{\Sigma}^{\top})^{-1}\bm{U}^{-1}$
$\displaystyle=\bm{V}\boldsymbol{\Sigma}^{\top}(\boldsymbol{\Sigma}\boldsymbol{\Sigma}^{\top})^{-1}\bm{U}^{-1}$
$\displaystyle=\bm{V}\boldsymbol{\Sigma}^{+}\bm{U}^{\top}.\qquad$
$\displaystyle(\boldsymbol{\Sigma}^{+}=\boldsymbol{\Sigma}^{\top}(\boldsymbol{\Sigma}\boldsymbol{\Sigma}^{\top})^{-1})$
$\bullet$ Case rank-deficient:
$\bm{X}^{+}=\bm{V}\boldsymbol{\Sigma}^{+}\bm{U}^{\top}$, where the upper-left
side of $\boldsymbol{\Sigma}^{+}\in^{p\times n}$ is a diagonal matrix
$diag(\frac{1}{\sigma_{1}},\frac{1}{\sigma_{2}},\cdots,\frac{1}{\sigma_{r}})$.
It can be easily verified that this definition of pseudo-inverse satisfies the
four criteria in Equation 6.

In either case, we have $\boldsymbol{\Sigma}^{+}$ as the pseudo-inverse of
$\boldsymbol{\Sigma}$ with $1/\sigma_{1},1/\sigma_{2},\cdots,1/\sigma_{r}$ on
its diagonal. We thus conclude the pseudo-inverse from SVD in the Table 2.

| $\bm{X}$ | $\bm{X}^{\top}$ | $\bm{X}^{+}$ | $\bm{A}^{+\top}$
---|---|---|---|---
SVD | $\bm{U}\boldsymbol{\Sigma}\bm{V}^{\top}$ | $\bm{V}\boldsymbol{\Sigma}\bm{U}^{\top}$ | $\bm{V}\boldsymbol{\Sigma}^{+}\bm{U}^{\top}$ | $\bm{U}\boldsymbol{\Sigma}^{+}\bm{V}^{\top}$
Table 2: Pseudo-inverse in SVD

From the pseudo-inverse via SVD, we can provide another way to see the
orthogonal projection in pseudo-inverse.  We have shown previously that
$\bm{H}=\bm{X}\bm{X}^{+}$ is an orthogonal projection, so we only need to show
that it projects onto $\mathcal{C}(\bm{X})$. For any vector $\bm{y}\in^{n}$,
we have $\bm{H}\bm{y}=\bm{X}\bm{X}^{+}\bm{y}=\bm{X}\boldsymbol{\beta}^{+},$
which is a linear combination of columns of $\bm{X}$. Thus
$\mathcal{C}(\bm{H})\subseteq\mathcal{C}(\bm{X})$. Moreover, since $\bm{H}$ is
a symmetric idempotent matrix, by Lemma 48, we have
$rank(\bm{H})=trace(\bm{H})=trace(\bm{X}\bm{X}^{+})=trace(\bm{U}\boldsymbol{\Sigma}\bm{V}^{\top}\bm{V}\boldsymbol{\Sigma}^{+}\bm{U}^{\top})=trace(\bm{U}\boldsymbol{\Sigma}\boldsymbol{\Sigma}^{+}\bm{U}^{\top})=r$,
where $\bm{U}\boldsymbol{\Sigma}\bm{V}^{\top}$ is the SVD of $\bm{X}$. Then
$\mathcal{C}(\bm{H})=\mathcal{C}(\bm{X})$ and we complete the proof.
Similarly, we can prove $\bm{P}=\bm{X}^{+}\bm{X}$ is the orthogonal projection
onto the row space of $\bm{X}$.

We finally prove the important property of the four subspaces in the pseudo-
inverse $\bm{X}^{+}$ via SVD. Firstly, we need to show the following lemma
that $\bm{X}^{+}\bm{X}^{+\top}$ and $\bm{X}^{+}$ have same rank.

######  Lemma 41 (Rank of $\bm{X}^{+}\bm{X}^{+\top}$)

$\bm{X}^{+}\bm{X}^{+\top}$ and $\bm{X}^{+}$ have same rank.

The claim in the lemma above and the proof are similar to Lemma 42.

Proof [of Lemma 41] Let $\boldsymbol{\beta}\in\mathcal{N}(\bm{X}^{+\top})$,
where $\bm{X}^{+\top}$ is the transpose of $\bm{X}^{+}$, we have

$\bm{X}^{+\top}\boldsymbol{\beta}=\boldsymbol{0}\qquad\underrightarrow{\text{leads
to}}\qquad\bm{X}^{+}\bm{X}^{+\top}\boldsymbol{\beta}=\boldsymbol{0},$

i.e.,
$\boldsymbol{\beta}\in\mathcal{N}(\bm{X}^{+\top})\,\,\,\,\underrightarrow{\text{leads
to}}\,\,\,\,\boldsymbol{\beta}\in\mathcal{N}(\bm{X}^{+}\bm{X}^{+\top})$,
therefore
$\mathcal{N}(\bm{X}^{+\top})\in\mathcal{N}(\bm{X}^{+}\bm{X}^{+\top})$.

Further, let $\boldsymbol{\beta}\in\mathcal{N}(\bm{X}^{+}\bm{X}^{+\top})$, we
have

$\bm{X}^{+}\bm{X}^{+\top}\boldsymbol{\beta}=\boldsymbol{0}\,\,\,\,\underrightarrow{\text{leads
to}}\,\,\,\,\boldsymbol{\beta}^{\top}\bm{X}^{+}\bm{X}^{+\top}\boldsymbol{\beta}=0\,\,\,\,\underrightarrow{\text{leads
to}}\,\,\,\,||\bm{X}^{+\top}\boldsymbol{\beta}||^{2}=0\,\,\,\,\underrightarrow{\text{leads
to}}\,\,\,\,\bm{X}^{+\top}\boldsymbol{\beta}=\boldsymbol{0},$

i.e.,
$\boldsymbol{\beta}\in\mathcal{N}(\bm{X}^{+}\bm{X}^{+\top})\,\,\,\,\underrightarrow{\text{leads
to}}\,\,\,\,\boldsymbol{\beta}\in\mathcal{N}(\bm{X}^{+\top}\boldsymbol{\beta})$,
therefore
$\mathcal{N}(\bm{X}^{+}\bm{X}^{+\top})\in\mathcal{N}(\bm{X}^{+\top})$. As a
result, $\mathcal{N}(\bm{X}^{+\top})=\mathcal{N}(\bm{X}^{+}\bm{X}^{+\top})$
and
$dim(\mathcal{N}(\bm{X}^{+\top}))=dim(\mathcal{N}(\bm{X}^{+}\bm{X}^{+\top}))$.
By fundamental theorem of linear algebra in Section 2.2,
$\bm{X}^{+}\bm{X}^{+\top}$ and $\bm{X}^{+}$ have same rank.
By the lemma above, we can provide another way to show the four subspaces in
pseudo-inverse.  From Lemma 51, for symmetric matrix
$\bm{X}^{+}\bm{X}^{+\top}=\bm{V}(\boldsymbol{\Sigma}^{\top}\boldsymbol{\Sigma})^{-1}\bm{V}^{\top}$,
$\mathcal{C}(\bm{X}^{+}\bm{X}^{+\top})$ is spanned by the eigenvectors, thus
$\\{\bm{v}_{1},\bm{v}_{2}\cdots,\bm{v}_{r}\\}$ is an orthonormal basis of
$\mathcal{C}(\bm{X}^{+}\bm{X}^{+\top})$. Since, 1\. $\bm{X}^{+}\bm{X}^{+\top}$
is symmetric, then the row space of $\bm{X}^{+}\bm{X}^{+\top}$ equals to the
column space of $\bm{X}^{+}\bm{X}^{+\top}$. 2\. All columns of
$\bm{X}^{+}\bm{X}^{+\top}$ are combination of columns of $\bm{X}^{+}$, so the
column space of $\bm{X}^{+}\bm{X}^{+\top}$ $\subseteq$ column space of
$\bm{X}^{+}$, i.e.,
$\mathcal{C}(\bm{X}^{+}\bm{X}^{+\top})\subseteq\mathcal{C}(\bm{X}^{+})$. 3\.
Since $rank(\bm{X}^{+}\bm{X}^{+\top})=rank(\bm{X}^{+})$ by Lemma 41, we then
have The row space of $\bm{X}^{+}\bm{X}^{+\top}$ = the column space of
$\bm{X}^{+}\bm{X}^{+\top}$ = the column space of $\bm{X}^{+}$, i.e.,
$\mathcal{C}(\bm{X}^{+}\bm{X}^{+\top})=\mathcal{C}(\bm{X}^{+})$. Thus
$\\{\bm{v}_{1},\bm{v}_{2},\cdots,\bm{v}_{r}\\}$ is an orthonormal basis of
$\mathcal{C}(\bm{X}^{+})$. We also proved in Lemma 16 that
$\\{\bm{v}_{1},\bm{v}_{2},\cdots,\bm{v}_{r}\\}$ is an orthonormal basis of the
row space of $\bm{X}$ (i.e., basis of $\mathcal{C}(\bm{X}^{\top})$). So
$\mathcal{C}(\bm{X}^{+})=\mathcal{C}(\bm{X}^{\top})$ as shown in Figure 9.
Similarly, if we apply this process to $\bm{X}^{+\top}\bm{X}^{+}$, we can show
the row space of $\bm{X}^{+}$ is equal to the column space of $\bm{X}$, and
the null space of $\bm{X}^{+}$ is equal to the null space of $\bm{X}^{\top}$.

Moreover, for $\boldsymbol{\beta}^{+}$ in row space of $\bm{X}$, we have
$\boldsymbol{\beta}^{+}=\sum_{i=1}^{r}x_{i}\bm{v}_{i}$ since
$\\{\bm{v}_{1},\bm{v}_{2},\cdots,\bm{v}_{r}\\}$ is an orthonormal basis for
the row space of $\bm{X}$. For vector
$\hat{\bm{y}}=\bm{X}\boldsymbol{\beta}^{+}$ in the column space of $\bm{X}$,
we have
$\hat{\bm{y}}=\bm{U}\boldsymbol{\Sigma}\bm{V}^{\top}\boldsymbol{\beta}^{+}$
and

$\bm{X}^{+}\hat{\bm{y}}=\bm{V}\boldsymbol{\Sigma}^{+}\bm{U}^{\top}\bm{U}\boldsymbol{\Sigma}\bm{V}^{\top}\boldsymbol{\beta}^{+}=\bm{V}\boldsymbol{\Sigma}^{+}\boldsymbol{\Sigma}\bm{V}^{\top}\boldsymbol{\beta}^{+}=(\sum_{i=1}^{r}\bm{v}_{i}\bm{v}_{i}^{\top})(\sum_{i=1}^{r}x_{i}\bm{v}_{i})=\sum_{i=1}^{r}x_{i}\bm{v}_{i}=\boldsymbol{\beta}^{+}.$

In conclude, for any vector $\boldsymbol{\beta}^{+}$ in row space of $\bm{X}$,
we have

$\hat{\bm{y}}=\bm{X}\boldsymbol{\beta}^{+}\qquad\underrightarrow{\text{leads
to}}\qquad\bm{X}^{+}\hat{\bm{y}}=\boldsymbol{\beta}^{+},$

and the relationship is depicted in Figure 9.

##  A Rank of a Special Symmetric Matrix

######  Lemma 42 (Rank of $\bm{X}^{\top}\bm{X}$)

For any matrix $\bm{X}$, $\bm{X}^{\top}\bm{X}$ and $\bm{X}$ have same rank.

Proof [of Lemma 42] Let $\boldsymbol{\eta}\in\mathcal{N}(\bm{X})$, we have

$\bm{X}\boldsymbol{\eta}=\boldsymbol{0}\qquad\underrightarrow{\text{leads
to}}\qquad\bm{X}^{\top}\bm{X}\boldsymbol{\eta}=\boldsymbol{0},$

i.e.,
$\boldsymbol{\eta}\in\mathcal{N}(\bm{X})\,\,\,\,\underrightarrow{\text{leads
to}}\,\,\,\,\boldsymbol{\eta}\in\mathcal{N}(\bm{X}^{\top}\bm{X})$. Therefore,
$\mathcal{N}(\bm{X})\in\mathcal{N}(\bm{X}^{\top}\bm{X})$.

Further, let $\boldsymbol{\eta}\in\mathcal{N}(\bm{X}^{\top}\bm{X})$, we have

$\bm{X}^{\top}\bm{X}\boldsymbol{\eta}=\boldsymbol{0}\,\,\,\,\underrightarrow{\text{leads
to}}\,\,\,\,\boldsymbol{\eta}^{\top}\bm{X}^{\top}\bm{X}\boldsymbol{\eta}=0\,\,\,\,\underrightarrow{\text{leads
to}}\,\,\,\,||\bm{X}\boldsymbol{\eta}||^{2}=0\,\,\,\,\underrightarrow{\text{leads
to}}\,\,\,\,\bm{X}\boldsymbol{\eta}=\boldsymbol{0},$

i.e.,
$\boldsymbol{\eta}\in\mathcal{N}(\bm{X}^{\top}\bm{X})\,\,\,\,\underrightarrow{\text{leads
to}}\,\,\,\,\boldsymbol{\eta}\in\mathcal{N}(\bm{X})$. Therefore,
$\mathcal{N}(\bm{X}^{\top}\bm{X})\in\mathcal{N}(\bm{X})$. As a result,
$\mathcal{N}(\bm{X})=\mathcal{N}(\bm{X}^{\top}\bm{X})$ and
$dim(\mathcal{N}(\bm{X}))=dim(\mathcal{N}(\bm{X}^{\top}\bm{X}))$. By
fundamental theorem of linear algebra in Section 2.2, $\bm{X}^{\top}\bm{X}$
and $\bm{X}$ have same rank.

##  B Similar Matrices

######  Definition 43 (Similar Matrices)

For any nonsingular matrix $\bm{P}$, the matrices $\bm{A}$ and
$\bm{P}\bm{A}\bm{P}^{-1}$ are called similar matrices.

######  Lemma 44 (Eigenvalue and Rank of Similar Matrices)

Any eigenvalue of $\bm{A}$ is also an eigenvalue of $\bm{P}\bm{A}\bm{P}^{-1}$
for any nonsingular matrix $\bm{P}$. The converse is also true that any
eigenvalue of $\bm{P}\bm{A}\bm{P}^{-1}$ is also an eigenvalue of $\bm{A}$.

And also the rank of $\bm{A}$ is equal to the rank of matrix
$\bm{P}\bm{A}\bm{P}^{-1}$ for any nonsingular matrix $\bm{P}$.

Proof [of Lemma 44] For any eigenvalue $\lambda$ of $\bm{A}$, we have
$\bm{A}\bm{x}=\lambda\bm{x}$. Then
$\lambda\bm{P}\bm{x}=\bm{P}\bm{A}\bm{P}^{-1}\bm{P}\bm{x}$ such that
$\bm{P}\bm{x}$ is an eigenvector of $\bm{P}\bm{A}\bm{P}^{-1}$ corresponding to
$\lambda$.

Similarly, for any eigenvalue $\lambda$ of $\bm{P}\bm{A}\bm{P}^{-1}$, we have
$\bm{P}\bm{A}\bm{P}^{-1}\bm{x}=\lambda\bm{x}$. Then
$\bm{A}\bm{P}^{-1}\bm{x}=\lambda\bm{P}^{-1}\bm{x}$ such that
$\bm{P}^{-1}\bm{x}$ is an eigenvector of $\bm{A}$ corresponding to $\lambda$.

For the rank of $\bm{P}\bm{A}\bm{P}^{-1}$, we have
$trace(\bm{P}\bm{A}\bm{P}^{-1})=trace(\bm{A}\bm{P}^{-1}\bm{P})=trace(\bm{A})$,
where the first equality comes from the fact that trace of a product is
invariant under cyclical permutations of the factors:

$\boxed{trace(\bm{A}\bm{B}\bm{C})=trace(\bm{B}\bm{C}\bm{A})=trace(\bm{C}\bm{A}\bm{B})},$

if all $\bm{A}\bm{B}\bm{C}$, $\bm{B}\bm{C}\bm{A}$, and $\bm{C}\bm{A}\bm{B}$
exist.

##  C Properties of Symmetric and Idempotent Matrices

Symmetric idempotent matrices have specific eigenvalues which will be often
used.

######  Lemma 45 (Eigenvalue of Symmetric Idempotent Matrices)

The only possible eigenvalues of any symmetric idempotent matrix are 0 and 1.

In Lemma 46, we prove the eigenvalues of idempotent matrices are 1 and 0 as
well which relaxes the conditions required here (both idempotent and
symmetric). However, the method used in the proof is quite useful so we keep
both of the claims.

Proof [of Lemma 45] Suppose matrix $\bm{A}$ is symmetric idempotent. By
spectral theorem (Theorem 49), we can decompose
$\bm{A}=\bm{Q}\boldsymbol{\Lambda}\bm{Q}^{\top}$, where $\bm{Q}$ is an
orthogonal matrix and $\boldsymbol{\Lambda}$ is a diagonal matrix. Therefore,

$\displaystyle(\bm{Q}\boldsymbol{\Lambda}\bm{Q}^{\top})^{2}$
$\displaystyle=\bm{Q}\boldsymbol{\Lambda}\bm{Q}$
$\displaystyle\bm{Q}\boldsymbol{\Lambda}\bm{Q}^{\top}\bm{Q}\boldsymbol{\Lambda}\bm{Q}^{\top}$
$\displaystyle=\bm{Q}\boldsymbol{\Lambda}\bm{Q}^{\top}$
$\displaystyle\bm{Q}\boldsymbol{\Lambda}^{2}\bm{Q}^{\top}$
$\displaystyle=\bm{Q}\boldsymbol{\Lambda}\bm{Q}^{\top}$
$\displaystyle\boldsymbol{\Lambda}^{2}$ $\displaystyle=\boldsymbol{\Lambda}$
$\displaystyle\lambda_{i}^{2}$ $\displaystyle=\lambda_{i}.$

Thus the eigenvalues of $\bm{A}$ satisfies that
$\lambda_{i}\in\\{0,1\\},\,\,\forall i$. We complete the proof.

In above lemma, we use spectral theorem to prove the only eigenvalues of any
symmetric idempotent matrices are 1 and 0. This trick from spectral theorem is
often used in mathematical proofs (see distribution theory sections in (Lu,
2021b)). By trivial trick, we can relax the condition from symmetric
idempotent to idempotent.

######  Lemma 46 (Eigenvalue of Idempotent Matrices)

The only possible eigenvalues of any idempotent matrix are 0 and 1.

Proof [of Lemma 46] Let $\bm{x}$ be an eigenvector of the idempotent matrix
$\bm{A}$ corresponding to eigenvalue $\lambda$. That is

$\bm{A}\bm{x}=\lambda\bm{x}.$

Also, we have

$\displaystyle\bm{A}^{2}\bm{x}$
$\displaystyle=(\bm{A}^{2})\bm{x}=\bm{A}\bm{x}=\lambda\bm{x}$
$\displaystyle=\bm{A}(\bm{A}\bm{x})=\bm{A}(\lambda\bm{x})=\lambda\bm{A}\bm{x}=\lambda^{2}\bm{x},$

which implies $\lambda^{2}=\lambda$ and $\lambda$ is 0 or 1.

We also prove the rank of a symmetric idempotent matrix.

######  Lemma 47 (Rank and Trace of Symmetric Idempotent Matrices)

For any $n\times n$ symmetric idempotent matrix $\bm{A}$, the rank of $\bm{A}$
equals to the trace of $\bm{A}$.

Proof [of Lemma 47] From spectral theorem 49, we have spectral decomposition
for $\bm{A}=\bm{Q}\boldsymbol{\Lambda}\bm{Q}^{\top}$. Since $\bm{A}$ and
$\boldsymbol{\Lambda}$ are similar matrices, their rank and trace are the same
(see Appendix B). That is,

$\displaystyle rank(\bm{A})$
$\displaystyle=rank(\mathrm{diag}(\lambda_{1},\lambda_{2},\cdots,\lambda_{n})),$
$\displaystyle trace(\bm{A})$
$\displaystyle=trace(\mathrm{diag}(\lambda_{1},\lambda_{2},\cdots,\lambda_{n})),$

By Lemma 45, the only eigenvalues of $\bm{A}$ are 0 and 1. Then,
$rank(\bm{A})=trace(\bm{A})$.

In above lemma, we prove the rank and trace of any symmetric idempotent matrix
are the same. However, it is rather a loose condition. We here also prove that
the only condition on idempotency has same result. Again, although this lemma
is a more general version, we provide both of them since the method used in
the proof is quite useful.

######  Lemma 48 (Rank and Trace of an Idempotent Matrix)

For any $n\times n$ idempotent matrix $\bm{A}$, the rank of $\bm{A}$ equals to
the trace of $\bm{A}$.

Proof [of Lemma 48] Any $n\times n$ rank-$r$ matrix $\bm{A}$ has CR
decomposition $\bm{A}=\bm{C}\bm{R}$, where $\bm{C}\in^{n\times r}$ and
$\bm{R}\in^{r\times n}$ with $\bm{C},\bm{R}$ having full rank $r$ (see (Lu,
2021a)).666CR decomposition: Any rank-$r$ matrix $\bm{A}\in^{n\times p}$ can
be factored as $\bm{A}=\bm{C}\bm{R}$, where $\bm{C}$ is some $r$ independent
columns of $\bm{A}$, and $\bm{R}$ is a $r\times p$ matrix to reconstruct the
columns of $\bm{A}$ from columns of $\bm{C}$. In particular, $\bm{R}$ is the
row reduced echelon form of $\bm{A}$ without the zero rows, and both $\bm{C}$
and $\bm{R}$ have full rank $r$. Then,

$\displaystyle\bm{A}^{2}$ $\displaystyle=\bm{A}$
$\displaystyle\bm{C}\bm{R}\bm{C}\bm{R}$ $\displaystyle=\bm{C}\bm{R}$
$\displaystyle\bm{R}\bm{C}\bm{R}$ $\displaystyle=\bm{R}$
$\displaystyle\bm{R}\bm{C}$ $\displaystyle=\bm{I}_{r},$

where $\bm{I}_{r}$ is a $r\times r$ identity matrix. Thus

$trace(\bm{A})=trace(\bm{C}\bm{R})=trace(\bm{R}\bm{C})=trace(\bm{I}_{r})=r,$

which equals to the rank of $\bm{A}$.

##  D Spectral Decomposition (Theorem)

In this section, we provide the proof for Theorem 49 which is essential for
the existence of singular value decomposition in the sequel.

######  Theorem 49 (Spectral Decomposition)

A real matrix $\bm{A}\in^{n\times n}$ is symmetric if and only if there exists
an orthogonal matrix $\bm{Q}$ and a diagonal matrix $\boldsymbol{\Lambda}$
such that

$\bm{A}=\bm{Q}\boldsymbol{\Lambda}\bm{Q}^{\top},$

where the columns of $\bm{Q}=[\bm{q}_{1},\bm{q}_{2},\cdots,\bm{q}_{n}]$ are
eigenvectors of $\bm{A}$ and orthonormal, and the entries of
$\boldsymbol{\Lambda}=diag(\lambda_{1},\lambda_{2},\cdots,\lambda_{n})$ are
the corresponding eigenvalues of $\bm{A}$, which are real. Specifically, we
have the following properties:

1\. A symmetric matrix has only real eigenvalues;

2\. The eigenvectors can be chosen orthonormal;

3\. The rank of $\bm{A}$ is the number of nonzero eigenvalues;

4\. If the eigenvalues are distinct, the eigenvectors are unique as well.

We prove the theorem in several steps.

Symmetric Matrix Property 1 of 4 The eigenvalues of any symmetric matrix are
all real.

Proof [All the eigenvalues of a real symmetric matrix are real] Suppose
eigenvalue $\lambda$ is a complex number $\lambda=a+ib$ where $a,b$ are real.
Its complex conjugate is $\bar{\lambda}=a-ib$. Same for complex eigenvector
$\boldsymbol{\beta}=\bm{c}+i\bm{d}$ and its complex conjugate
$\bar{\boldsymbol{\beta}}=\bm{c}-i\bm{d}$ where $\bm{c},\bm{d}$ are real
vectors. We then have the following property

$\bm{X}\boldsymbol{\beta}=\lambda\boldsymbol{\beta}\qquad\underrightarrow{\text{
leads to
}}\qquad\bm{X}\bar{\boldsymbol{\beta}}=\bar{\lambda}\bar{\boldsymbol{\beta}}\qquad\underrightarrow{\text{
transpose to
}}\qquad\bar{\boldsymbol{\beta}}^{\top}\bm{X}=\bar{\lambda}\bar{\boldsymbol{\beta}}^{\top}.$

We take dot product of the first equation with $\bar{\boldsymbol{\beta}}$ and
the last equation with $\boldsymbol{\beta}$:

$\bar{\boldsymbol{\beta}}^{\top}\bm{X}\boldsymbol{\beta}=\lambda\bar{\boldsymbol{\beta}}^{\top}\boldsymbol{\beta},\qquad\text{and
}\qquad\bar{\boldsymbol{\beta}}^{\top}\bm{X}\boldsymbol{\beta}=\bar{\lambda}\bar{\boldsymbol{\beta}}^{\top}\boldsymbol{\beta}.$

Then we have the equality
$\lambda\bar{\boldsymbol{\beta}}^{\top}\boldsymbol{\beta}=\bar{\lambda}\bar{\boldsymbol{\beta}}^{\top}\boldsymbol{\beta}$.
Since
$\bar{\boldsymbol{\beta}}^{\top}\boldsymbol{\beta}=(\bm{c}-i\bm{d})^{\top}(\bm{c}+i\bm{d})=\bm{c}^{\top}\bm{c}+\bm{d}^{\top}\bm{d}$
is a real number. Therefore the imaginary part of $\lambda$ is zero and
$\lambda$ is real.

Symmetric Matrix Property 2 of 4 The eigenvectors corresponding to distinct
eigenvalues of any symmetric matrix are orthogonal so that we can normalize
eigenvectors to make them orthonormal since
$\bm{X}\boldsymbol{\beta}=\lambda\boldsymbol{\beta}\underrightarrow{\text{
leads to
}}\bm{X}\frac{\boldsymbol{\beta}}{||\boldsymbol{\beta}||}=\lambda\frac{\boldsymbol{\beta}}{||\boldsymbol{\beta}||}$
which corresponds to the same eigenvalue.

Proof [The eigenvectors are orthogonal] Suppose eigenvalues
$\lambda_{1},\lambda_{2}$ correspond to eigenvectors
$\boldsymbol{\beta}_{1},\boldsymbol{\beta}_{2}$ so that
$\bm{X}\boldsymbol{\beta}_{1}=\lambda\boldsymbol{\beta}_{1}$ and
$\bm{X}\boldsymbol{\beta}_{2}=\lambda_{2}\boldsymbol{\beta}_{2}$. We have the
following equality:

$\bm{X}\boldsymbol{\beta}_{1}=\lambda_{1}\boldsymbol{\beta}_{1}\qquad\underrightarrow{\text{leads
to}}\qquad\boldsymbol{\beta}_{1}^{\top}\bm{X}=\lambda_{1}\boldsymbol{\beta}_{1}^{\top}\qquad\underrightarrow{\text{leads
to}}\qquad\boldsymbol{\beta}_{1}^{\top}\bm{X}\boldsymbol{\beta}_{2}=\lambda_{1}\boldsymbol{\beta}_{1}^{\top}\boldsymbol{\beta}_{2},$

and

$\bm{X}\boldsymbol{\beta}_{2}=\lambda_{2}\boldsymbol{\beta}_{2}\qquad\underrightarrow{\text{leads
to}}\qquad\boldsymbol{\beta}_{1}^{\top}\bm{X}\boldsymbol{\beta}_{2}=\lambda_{2}\boldsymbol{\beta}_{1}^{\top}\boldsymbol{\beta}_{2},$

which implies
$\lambda_{1}\boldsymbol{\beta}_{1}^{\top}\boldsymbol{\beta}_{2}=\lambda_{2}\boldsymbol{\beta}_{1}^{\top}\boldsymbol{\beta}_{2}$.
Since eigenvalues $\lambda_{1}\neq\lambda_{2}$, the eigenvectors are
orthogonal.

For any matrix multiplication we have the rank of the multiplication result no
larger than the rank of the inputs. However, the symmetric matrix
$\bm{X}^{\top}\bm{X}$ is rather special that the rank of $\bm{X}^{\top}\bm{X}$
is equal to that of $\bm{X}$ which will be used in the proof of singular value
decomposition in the next section.

######  Lemma 50 (Rank of $\bm{X}\bm{Y}$)

For any matrix $\bm{X}\in^{m\times n}$, $\bm{Y}\in^{n\times k}$, then the
matrix multiplication $\bm{X}\bm{Y}\in^{m\times k}$ has
$rank$($\bm{X}\bm{Y}$)$\leq$min($rank$($\bm{X}$), $rank$($\bm{Y}$)).

Proof [of Lemma 50] For matrix multiplication $\bm{X}\bm{Y}$, we have

$\bullet$ All rows of $\bm{X}\bm{Y}$ are combination of the rows of $\bm{Y}$,
the row space of $\bm{X}\bm{Y}$ is a subset of the row space of $\bm{Y}$. Thus
$rank$($\bm{X}\bm{Y}$)$\leq$$rank$($\bm{Y}$).

$\bullet$ All columns of $\bm{X}\bm{Y}$ are combination of columns of
$\bm{X}$, the column space of $\bm{X}\bm{Y}$ is a subset of the column space
of $\bm{X}$. Thus $rank$($\bm{X}\bm{Y}$)$\leq$$rank$($\bm{X}$).

Therefore we have, $rank$($\bm{X}\bm{Y}$)$\leq$min($rank$($\bm{X}$),
$rank$($\bm{Y}$)).

Symmetric Matrix Property 3 of 4

######  Lemma 51 (Rank of Symmetric Matrix)

If $\bm{X}$ is an $n\times n$ real symmetric matrix, then rank($\bm{X}$) = the
total number of nonzero eigenvalues of $\bm{X}$. In particular, $\bm{X}$ has
full rank if and only if $\bm{X}$ is nonsingular. Further,
$\mathcal{C}(\bm{X})$ is the linear space spanned by the eigenvectors of
$\bm{X}$ that correspond to nonzero eigenvalues.

Proof [of Lemma 51] For any symmetric matrix $\bm{X}$, we have $\bm{X}$, in
spectral form, as $\bm{X}=\bm{Q}\boldsymbol{\Lambda}\bm{Q}^{\top}$ and also
$\boldsymbol{\Lambda}=\bm{Q}^{\top}\bm{X}\bm{Q}$. Since we have shown in Lemma
50 that the rank of the matrix multiplication
$rank$($\bm{X}\bm{Y}$)$\leq$min($rank$($\bm{X}$), $rank$($\bm{Y}$)).

$\bullet$ From $\bm{X}=\bm{Q}\boldsymbol{\Lambda}\bm{Q}^{\top}$, we have
$rank(\bm{X})\leq rank(\bm{Q}\boldsymbol{\Lambda})\leq
rank(\boldsymbol{\Lambda})$;

$\bullet$ From $\boldsymbol{\Lambda}=\bm{Q}^{\top}\bm{X}\bm{Q}$, we have
$rank(\boldsymbol{\Lambda})\leq rank(\bm{Q}^{\top}\bm{X})\leq rank(\bm{X})$,

The inequalities above give us contradiction. And thus
$rank(\bm{X})=rank(\boldsymbol{\Lambda})$ which is the total number of nonzero
eigenvalues.

Since $\bm{X}$ is nonsingular if and only if all of its eigenvalues are
nonzero, $\bm{X}$ has full rank if and only if $\bm{X}$ is nonsingular.

For the fourth property of symmetric matrix, we need the definition of similar
matrices and the property about eigenvalues of similar matrices (see Appendix
B).

Symmetric Matrix Property 4 of 4

######  Lemma 52 (Orthonormal Eigenvectors for Duplicate Eigenvalue)

If $\bm{X}$ has a duplicate eigenvalue $\lambda_{i}$ with multiplicity $k\geq
2$, then there exist $k$ orthonormal eigenvectors corresponding to
$\lambda_{i}$.

Proof [of Lemma 52] We note that there is at least one eigenvector
$\boldsymbol{\beta}_{i1}$ corresponding to $\lambda_{i}$. And for such
eigenvector $\boldsymbol{\beta}_{i1}$, we can always find additional $n-1$
orthonormal vectors $\bm{y}_{2},\bm{y}_{3},\cdots,\bm{y}_{n}$ so that
$\\{\boldsymbol{\beta}_{i1},\bm{y}_{2},\bm{y}_{3},\cdots,\bm{y}_{n}\\}$ forms
an orthonormal basis in n. Put the $\bm{y}_{2},\bm{y}_{3},\cdots,\bm{y}_{n}$
into matrix $\bm{Y}_{1}$ and
$\\{\boldsymbol{\beta}_{i1},\bm{y}_{2},\bm{y}_{3},\cdots,\bm{y}_{n}\\}$ into
matrix $\bm{P}_{1}$

$\bm{Y}_{1}=[\bm{y}_{2},\bm{y}_{3},\cdots,\bm{y}_{n}]\qquad\text{and}\qquad\bm{P}_{1}=[\boldsymbol{\beta}_{i1},\bm{Y}_{1}].$

We then have

$\bm{P}_{1}^{\top}\bm{X}\bm{P}_{1}=\begin{bmatrix}\lambda_{i}&\boldsymbol{0}\\\
\boldsymbol{0}&\bm{Y}_{1}^{\top}\bm{X}\bm{Y}_{1}\end{bmatrix}=\begin{bmatrix}\lambda_{i}&\boldsymbol{0}\\\
\boldsymbol{0}&\bm{B}\end{bmatrix}.\qquad(\text{Let
$\bm{B}=\bm{Y}_{1}^{\top}\bm{X}\bm{Y}_{1}$})$

As a result, $\bm{X}$ and $\bm{P}_{1}^{\top}\bm{X}\bm{P}_{1}$ are similar
matrices such that they have same eigenvalues since $\bm{P}_{1}$ is
nonsingular (even orthogonal here, see Lemma 44). We obtain

$\det(\bm{P}_{1}^{\top}\bm{X}\bm{P}_{1}-\lambda\bm{I}_{n})=(\lambda_{i}-\lambda)\det(\bm{Y}_{1}^{\top}\bm{X}\bm{Y}_{1}-\lambda\bm{I}_{n-1}).$

If $\lambda_{i}$ has multiplicity $k\geq 2$, then the term
$(\lambda_{i}-\lambda)$ occurs $k$ times in the polynomial from the
determinant $\det(\bm{P}_{1}^{\top}\bm{X}\bm{P}_{1}-\lambda\bm{I}_{n})$, i.e.,
the term occurs $k-1$ times in the polynomial from
$\det(\bm{Y}_{1}^{\top}\bm{X}\bm{Y}_{1}-\lambda\bm{I}_{n-1})$. In another
word, $\det(\bm{Y}_{1}^{\top}\bm{X}\bm{Y}_{1}-\lambda_{i}\bm{I}_{n-1})=0$ and
$\lambda_{i}$ is an eigenvalue of $\bm{Y}_{1}^{\top}\bm{X}\bm{Y}_{1}$.

Let $\bm{B}=\bm{Y}_{1}^{\top}\bm{X}\bm{Y}_{1}$. Since
$\det(\bm{B}-\lambda_{i}\bm{I}_{n-1})=0$, the null space of
$\bm{B}-\lambda_{i}\bm{I}_{n-1}$ is not none. Suppose
$(\bm{B}-\lambda_{i}\bm{I}_{n-1})\bm{n}=\boldsymbol{0}$, i.e.,
$\bm{B}\bm{n}=\lambda_{i}\bm{n}$ and $\bm{n}$ is an eigenvector of $\bm{B}$.

From
$\bm{P}_{1}^{\top}\bm{X}\bm{P}_{1}=\begin{bmatrix}\lambda_{i}&\boldsymbol{0}\\\
\boldsymbol{0}&\bm{B}\end{bmatrix},$ we have
$\bm{X}\bm{P}_{1}\begin{bmatrix}z\\\
\bm{n}\end{bmatrix}=\bm{P}_{1}\begin{bmatrix}\lambda_{i}&\boldsymbol{0}\\\
\boldsymbol{0}&\bm{B}\end{bmatrix}\begin{bmatrix}z\\\ \bm{n}\end{bmatrix}$,
where $z$ is any scalar. From the left side of this equation, we have

$\displaystyle\bm{X}\bm{P}_{1}\begin{bmatrix}z\\\ \bm{n}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\lambda_{i}\boldsymbol{\beta}_{i1},\bm{X}\bm{Y}_{1}\end{bmatrix}\begin{bmatrix}z\\\
\bm{n}\end{bmatrix}$ (8)
$\displaystyle=\lambda_{i}z\boldsymbol{\beta}_{i1}+\bm{X}\bm{Y}_{1}\bm{n}.$

And from the right side of the equation, we have

$\displaystyle\bm{P}_{1}\begin{bmatrix}\lambda_{i}&\boldsymbol{0}\\\
\boldsymbol{0}&\bm{B}\end{bmatrix}\begin{bmatrix}z\\\ \bm{n}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\boldsymbol{\beta}_{i1}&\bm{Y}_{1}\end{bmatrix}\begin{bmatrix}\lambda_{i}&\boldsymbol{0}\\\
\boldsymbol{0}&\bm{B}\end{bmatrix}\begin{bmatrix}z\\\ \bm{n}\end{bmatrix}$ (9)
$\displaystyle=\begin{bmatrix}\lambda_{i}\boldsymbol{\beta}_{i1}&\bm{Y}_{1}\bm{B}\end{bmatrix}\begin{bmatrix}z\\\
\bm{n}\end{bmatrix}$
$\displaystyle=\lambda_{i}z\boldsymbol{\beta}_{i1}+\bm{Y}_{1}\bm{B}\bm{n}$
$\displaystyle=\lambda_{i}z\boldsymbol{\beta}_{i1}+\lambda_{i}\bm{Y}_{1}\bm{n}.\qquad(\text{Since
$\bm{B}\bm{n}=\lambda_{i}\bm{n}$})$

Combine Equation 9 and Equation 8, we obtain

$\bm{X}\bm{Y}_{1}\bm{n}=\lambda_{i}\bm{Y}_{1}\bm{n},$

which means $\bm{Y}_{1}\bm{n}$ is an eigenvector of $\bm{X}$ corresponding to
the eigenvalue $\lambda_{i}$ (same eigenvalue corresponding to
$\boldsymbol{\beta}_{i1}$). Since $\bm{Y}_{1}\bm{n}$ is a combination of
$\bm{y}_{2},\bm{y}_{3},\cdots,\bm{y}_{n}$ which are orthonormal to
$\boldsymbol{\beta}_{i1}$, the $\bm{Y}_{1}\bm{n}$ can be chosen to be
orthonormal to $\boldsymbol{\beta}_{i1}$.

To conclude, if we have one eigenvector $\boldsymbol{\beta}_{i1}$
corresponding to $\lambda_{i}$ whose multiplicity is $k\geq 2$, we could
construct the second eigenvector by choosing one vector from null space of
$(\bm{B}-\lambda_{i}\bm{I}_{n-1})$ constructed above. Suppose now, we have
constructed the second eigenvector $\boldsymbol{\beta}_{i2}$ which is
orthonormal to $\boldsymbol{\beta}_{i1}$. For such eigenvectors
$\boldsymbol{\beta}_{i1},\boldsymbol{\beta}_{i2}$, we can always find
additional $n-2$ orthonormal vectors $\bm{y}_{3},\bm{y}_{4},\cdots,\bm{y}_{n}$
so that
$\\{\boldsymbol{\beta}_{i1},\boldsymbol{\beta}_{i2},\bm{y}_{3},\bm{y}_{4},\cdots,\bm{y}_{n}\\}$
forms an orthonormal basis in n. Put the
$\bm{y}_{3},\bm{y}_{4},\cdots,\bm{y}_{n}$ into matrix $\bm{Y}_{2}$ and
$\\{\boldsymbol{\beta}_{i1},\boldsymbol{\beta}_{i2},\bm{y}_{3},\bm{y}_{4},\cdots,\bm{y}_{n}\\}$
into matrix $\bm{P}_{2}$:

$\bm{Y}_{2}=[\bm{y}_{3},\bm{y}_{4},\cdots,\bm{y}_{n}]\qquad\text{and}\qquad\bm{P}_{2}=[\boldsymbol{\beta}_{i1},\boldsymbol{\beta}_{i2},\bm{Y}_{1}].$

We then have

$\bm{P}_{2}^{\top}\bm{X}\bm{P}_{2}=\begin{bmatrix}\lambda_{i}&0&\boldsymbol{0}\\\
0&\lambda_{i}&\boldsymbol{0}\\\
\boldsymbol{0}&\boldsymbol{0}&\bm{Y}_{2}^{\top}\bm{X}\bm{Y}_{2}\end{bmatrix}=\begin{bmatrix}\lambda_{i}&0&\boldsymbol{0}\\\
0&\lambda_{i}&\boldsymbol{0}\\\
\boldsymbol{0}&\boldsymbol{0}&\bm{C}\end{bmatrix},$

where $\bm{C}=\bm{Y}_{2}^{\top}\bm{X}\bm{Y}_{2}$ such that
$\det(\bm{P}_{2}^{\top}\bm{X}\bm{P}_{2}-\lambda\bm{I}_{n})=(\lambda_{i}-\lambda)^{2}\det(\bm{C}-\lambda\bm{I}_{n-2})$.
If the multiplicity of $\lambda_{i}$ is $k\geq 3$,
$\det(\bm{C}-\lambda_{i}\bm{I}_{n-2})=0$ and the null space of
$\bm{C}-\lambda_{i}\bm{I}_{n-2}$ is not none so that we can still find a
vector from null space of $\bm{C}-\lambda_{i}\bm{I}_{n-2}$ and
$\bm{C}\bm{n}=\lambda_{i}\bm{n}$. Now we can construct a vector
$\begin{bmatrix}z_{1}\\\ z_{2}\\\ \bm{n}\end{bmatrix}\in^{n}$, where
$z_{1},z_{2}$ are any scalar values, such that

$\bm{X}\bm{P}_{2}\begin{bmatrix}z_{1}\\\ z_{2}\\\
\bm{n}\end{bmatrix}=\bm{P}_{2}\begin{bmatrix}\lambda_{i}&0&\boldsymbol{0}\\\
0&\lambda_{i}&\boldsymbol{0}\\\
\boldsymbol{0}&\boldsymbol{0}&\bm{C}\end{bmatrix}\begin{bmatrix}z_{1}\\\
z_{2}\\\ \bm{n}\end{bmatrix}.$

Similarly, from the left side of above equation we will get
$\lambda_{i}z_{1}\boldsymbol{\beta}_{i1}+\lambda_{i}z_{2}\boldsymbol{\beta}_{i2}+\bm{X}\bm{Y}_{2}\bm{n}$.
From the right side of above equation we will get
$\lambda_{i}z_{1}\boldsymbol{\beta}_{i1}+\lambda_{i}z_{2}\boldsymbol{\beta}_{i2}+\lambda_{i}\bm{Y}_{2}\bm{n}$.
As a result,

$\bm{X}\bm{Y}_{2}\bm{n}=\lambda_{i}\bm{Y}_{2}\bm{n},$

where $\bm{Y}_{2}\bm{n}$ is an eigenvector of $\bm{X}$ and orthogonal to
$\boldsymbol{\beta}_{i1},\boldsymbol{\beta}_{i2}$. And it is easy to construct
the eigenvector to be orthonormal to the first two.

The process can go on, and finally, we will find $k$ orthonormal eigenvectors
corresponding to $\lambda_{i}$.

Actually, the dimension of the null space of
$\bm{P}_{1}^{\top}\bm{X}\bm{P}_{1}-\lambda_{i}\bm{I}_{n}$ is equal to the
multiplicity $k$. It also follows that if the multiplicity of $\lambda_{i}$ is
$k$, there cannot be more than $k$ orthogonal eigenvectors corresponding to
$\lambda_{i}$. Otherwise, it will come to the conclusion that we could find
more than $n$ orthogonal eigenvectors which leads to a contradiction.

The proof of Theorem 49 is trivial from the lemmas above. Also, we can use
Schur decomposition to prove the existence of spectral decomposition (see (Lu,
2021a)).

##  E Singular Value Decomposition (SVD)

######  Theorem 53 (Reduced SVD for Rectangular Matrices)

For every real $n\times p$ matrix $\bm{X}$ with rank $r$, then matrix $\bm{X}$
can be factored as

$\bm{X}=\bm{U}\boldsymbol{\Sigma}\bm{V}^{\top},$

where $\boldsymbol{\Sigma}\in^{r\times r}$ is a diagonal matrix
$\boldsymbol{\Sigma}=diag(\sigma_{1},\sigma_{2}\cdots,\sigma_{r})$ with
$\sigma_{1}\geq\sigma_{2}\geq\cdots\geq\sigma_{r}$ and

$\bullet$ $\sigma_{i}$’s are the nonzero singular values of $\bm{X}$, in the
meantime, they are the (positive) square roots of the nonzero eigenvalues of
$\bm{X}^{\top}\bm{X}$ and $\bm{X}\bm{X}^{\top}$.

$\bullet$ Columns of $\bm{U}\in^{n\times r}$ contain the $r$ eigenvectors of
$\bm{X}\bm{X}^{\top}$ corresponding to the $r$ nonzero eigenvalues of
$\bm{X}\bm{X}^{\top}$.

$\bullet$ Columns of $\bm{V}\in^{p\times r}$ contain the $r$ eigenvectors of
$\bm{X}^{\top}\bm{X}$ corresponding to the $r$ nonzero eigenvalues of
$\bm{X}^{\top}\bm{X}$.

$\bullet$ Moreover, the columns of $\bm{U}$ and $\bm{V}$ are called the left
and right singular vectors of $\bm{X}$, respectively.

$\bullet$ Further, the columns of $\bm{U}$ and $\bm{V}$ are orthonormal (by
Spectral Theorem 49).

In particular, we can write out the matrix decomposition
$\bm{X}=\bm{U}\boldsymbol{\Sigma}\bm{V}^{\top}=\sum_{i=1}^{r}\sigma_{i}\bm{u}_{i}\bm{v}_{i}^{\top}$,
which is a sum of $r$ rank-one matrices.

If we append additional $n-r$ silent columns that are orthonormal to the $r$
eigenvectors of $\bm{X}\bm{X}^{\top}$, we will have an orthogonal matrix
$\bm{U}\in^{n\times n}$. Similar for the columns of $\bm{V}$. We then
illustrate the full SVD for matrices in Theorem 15 where we formulate the
difference between reduced and full SVD in the blue text.

The comparison of reduced and full SVD is shown in Figure 2 where white
entries are zero and blue entries are not necessarily zero.

To prove the existence of the SVD, we need to use the following lemmas. We
mentioned that the singular values are the square roots of the eigenvalues of
$\bm{X}^{\top}\bm{X}$. While, negative values do not have square roots such
that the eigenvalues must be nonnegative.

######  Lemma 54 (Nonnegative Eigenvalues of $\bm{X}^{\top}\bm{X}$)

For any matrix $\bm{X}\in^{n\times p}$, $\bm{X}^{\top}\bm{X}$ has nonnegative
eigenvalues.

Proof [of Lemma 54] For eigenvalue and its corresponding eigenvector
$\lambda,\boldsymbol{\beta}$ of $\bm{X}^{\top}\bm{X}$, we have

$\bm{X}^{\top}\bm{X}\boldsymbol{\beta}=\lambda\boldsymbol{\beta}\qquad\underrightarrow{\text{leads
to}}\qquad\boldsymbol{\beta}^{\top}\bm{X}^{\top}\bm{X}\boldsymbol{\beta}=\lambda\boldsymbol{\beta}^{\top}\boldsymbol{\beta}.$

Since
$\boldsymbol{\beta}^{\top}\bm{X}^{\top}\bm{X}\boldsymbol{\beta}=||\bm{X}\boldsymbol{\beta}||^{2}\geq
0$ and $\boldsymbol{\beta}^{\top}\boldsymbol{\beta}\geq 0$. We then have
$\lambda\geq 0$.

Since $\bm{X}^{\top}\bm{X}$ has nonnegative eigenvalues, we then can define
the singular value $\sigma\geq 0$ of $\bm{X}$ such that $\sigma^{2}$ is the
eigenvalue of $\bm{X}^{\top}\bm{X}$, i.e.,
$\bm{X}^{\top}\bm{X}\bm{v}=\sigma^{2}\bm{v}$. This is essential to SVD.

We have shown in Lemma 50 that
$rank$($\bm{X}\bm{B}$)$\leq$min($rank$($\bm{X}$), $rank$($\bm{B}$)). However,
the symmetric matrix $\bm{X}^{\top}\bm{X}$ is rather special that the rank of
$\bm{X}^{\top}\bm{X}$ is equal to $rank(\bm{X})$. And the proof is provided in
Lemma 42.

In the form of SVD, we claimed the matrix $\bm{X}$ is a sum of $r$ rank-one
matrices where $r$ is the number of nonzero singular values. And the number of
nonzero singular values is actually the rank of the matrix.

######  Lemma 55 (The Number of Nonzero Singular Values Equals to the Rank)

The number of nonzero singular values of matrix $\bm{X}$ equals the rank of
$\bm{X}$.

Proof [of Lemma 55] The rank of any symmetric matrix (here
$\bm{X}^{\top}\bm{X}$) equals the number of nonzero eigenvalues (with
repetitions) by Lemma 51. So the number of nonzero singular values equals the
rank of $\bm{X}^{\top}\bm{X}$. By Lemma 42, $\bm{X}^{\top}\bm{X}$ and $\bm{X}$
have same rank, so the number of nonzero singular values equals to the rank of
$\bm{X}$.

We are now ready to prove the existence of SVD.

Proof [of Theorem 53: Existence of the SVD] Since $\bm{X}^{\top}\bm{X}$ is a
symmetric matrix, by Spectral Theorem 49 and Lemma 54, there exists an
orthogonal matrix $\bm{V}$ such that

$\boxed{\bm{X}^{\top}\bm{X}=\bm{V}\boldsymbol{\Sigma}^{2}\bm{V}^{\top}},$

where $\boldsymbol{\Sigma}$ is a diagonal matrix containing the singular
values of $\bm{A}$, i.e., $\boldsymbol{\Sigma}^{2}$ contains the eigenvalues
of $\bm{A}^{\top}\bm{A}$. Specifically,
$\boldsymbol{\Sigma}=diag(\sigma_{1},\sigma_{2}\cdots,\sigma_{r})$ and
$\\{\sigma_{1}^{2},\sigma_{2}^{2},\cdots,\sigma_{r}^{2}\\}$ are the nonzero
eigenvalues of $\bm{A}^{\top}\bm{A}$ with $r$ being the rank of $\bm{A}$.
I.e., $\\{\sigma_{1},\cdots,\sigma_{r}\\}$ are the singular values of
$\bm{A}$. In this case, $\bm{V}\in^{p\times r}$. Now we are into the central
part.  Start from $\bm{X}^{\top}\bm{X}\bm{v}_{i}=\sigma_{i}^{2}\bm{v}_{i}$,
$\forall i\in\\{1,2,\cdots,r\\}$, i.e., the eigenvector $\bm{v}_{i}$ of
$\bm{X}^{\top}\bm{X}$ corresponding to $\sigma_{i}^{2}$: 1\. Multiply both
sides by $\bm{v}_{i}^{\top}$:
$\bm{v}_{i}^{\top}\bm{X}^{\top}\bm{X}\bm{v}_{i}=\sigma_{i}^{2}\bm{v}_{i}^{\top}\bm{v}_{i}\qquad\underrightarrow{\text{leads
to}}\qquad||\bm{X}\bm{v}_{i}||^{2}=\sigma_{i}^{2}\qquad\underrightarrow{\text{leads
to}}\qquad||\bm{X}\bm{v}_{i}||=\sigma_{i}.$ 2\. Multiply both sides by
$\bm{X}$:
$\bm{X}\bm{X}^{\top}\bm{X}\bm{v}_{i}=\sigma_{i}^{2}\bm{X}\bm{v}_{i}\,\,\,\,\underrightarrow{\text{leads
to}}\,\,\,\,\bm{X}\bm{X}^{\top}\frac{\bm{X}\bm{v}_{i}}{\sigma_{i}}=\sigma_{i}^{2}\frac{\bm{X}\bm{v}_{i}}{\sigma_{i}}\,\,\,\,\underrightarrow{\text{leads
to}}\,\,\,\,\bm{X}\bm{X}^{\top}\bm{u}_{i}=\sigma_{i}^{2}\bm{u}_{i},$ where we
notice this form can find the eigenvector of $\bm{X}\bm{X}^{\top}$
corresponding to $\sigma_{i}^{2}$ which is $\bm{X}\bm{v}_{i}$. Since the
length of $\bm{X}\bm{v}_{i}$ is $\sigma_{i}$, we then define
$\bm{u}_{i}=\frac{\bm{X}\bm{v}_{i}}{\sigma_{i}}$ with norm 1. These
$\bm{u}_{i}$’s are orthogonal because
$(\bm{X}\bm{v}_{i})^{\top}(\bm{X}\bm{v}_{j})=\bm{v}_{i}^{\top}\bm{X}^{\top}\bm{X}\bm{v}_{j}=\sigma_{j}^{2}\bm{v}_{i}^{\top}\bm{v}_{j}=0$.
That is

$\boxed{\bm{X}\bm{X}^{\top}=\bm{U}\boldsymbol{\Sigma}^{2}\bm{U}^{\top}}.$

Since $\bm{X}\bm{v}_{i}=\sigma_{i}\bm{u}_{i}$, we have

$[\bm{X}\bm{v}_{1},\bm{X}\bm{v}_{2},\cdots,\bm{X}\bm{v}_{r}]=[\sigma_{1}\bm{u}_{1},\sigma_{2}\bm{u}_{2},\cdots,\sigma_{r}\bm{u}_{r}]\qquad\underrightarrow{\text{leads
to}}\qquad\bm{X}\bm{V}=\bm{U}\boldsymbol{\Sigma},$

which completes the proof.
By appending silent columns in $\bm{U}$ and $\bm{V}$, we can easily find the
full SVD.

## References

  * Bishop (2006) Christopher M Bishop.  Pattern recognition.  _Machine learning_ , 128(9), 2006.
  * Lu (2021a) Jun Lu.  Numerical matrix decomposition and its modern applications: A rigorous first course.  _arXiv preprint arXiv:2107.02579_ , 2021a.
  * Lu (2021b) Jun Lu.  A rigorous introduction for linear models.  _arXiv preprint arXiv:2105.04240_ , 2021b.
  * Rose (1982) Nicholas J Rose.  Linear algebra and its applications (gilbert strang).  _SIAM Review_ , 24(4):499–501, 1982.
  * Strang (1993) Gilbert Strang.  The fundamental theorem of linear algebra.  _The American Mathematical Monthly_ , 100(9):848–855, 1993.
  * Strang (2009) Gilbert Strang.  _Introduction to linear algebra_.  Wellesley-Cambridge Press Wellesley, 4th edition, 2009.
  * Strang (2019) Gilbert Strang.  _Linear algebra and learning from data_.  Wellesley-Cambridge Press Cambridge, 2019.
  * Strang (2021) Gilbert Strang.  _Linear algebra for everyone_.  Wellesley-Cambridge Press Wellesley, 2021.
  * Trefethen and Bau III (1997) Lloyd N Trefethen and David Bau III.  _Numerical linear algebra_ , volume 50.  Siam, 1997.