\section{The Theorem}\label{append:row-equal-column}



In normal conditions, what we talk about the rank of a matrix $\bm{A}\in \mathbb{R}^{m\times n}$ refers to 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}$. By the following theorem, this 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\{m,n\}$. 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 \mathbb{R}^m$ and a vector $\bm{v} \in \mathbb{R}^n$, then the $m\times n$ matrix $\bm{u}\bm{v}^\top$ is of rank 1.
We here present the theorem rigorously as follows:
\begin{mdframed}[hidealllines=true,backgroundcolor=color1]
	\begin{theorem}[Row Rank Equals to Column Rank]\label{lemma:equal-dimension-rank}
		The dimension of the column space of a matrix $\bm{A}\in \mathbb{R}^{m\times n}$ is equal to the dimension of its
		row space, i.e., the row rank and the column rank of a matrix $\bm{A}$ are equal.
	\end{theorem}
\end{mdframed}

This paper offers three ways to prove the equivalence of the row and column ranks:
\begin{itemize}
\item An elementary way that constructs column basis from row basis;

\item A Gram-Schmidt way that results in the UTV decomposition framework which in turn gives insights on the theorem;

\item A column-row decomposition way that arises from Gaussian elimination.
\end{itemize}

\section{An Elementary Way}
In this section, we prove Theorem~\ref{lemma:equal-dimension-rank} by an elementary approach from which it also reveals the fundamental theorem of linear algebra.

\begin{proof}[of Theorem~\ref{lemma:equal-dimension-rank}, \textbf{The First Way: An Elementary Way}]
	We first notice that the null space of $\bm{A}$ \footnote{Null space of $\bm{A}$, denoted as $\mathcal{N}(\bm{A})$; and column space of $\bm{A}$, denoted as $\mathcal{C}(\bm{A})$.} is orthogonal complementary to the row space of $\bm{A}$ ($\mathcal{C}(\bm{A}^\top)$, i.e., the column space of $\bm{A}^\top$, where the row space of $\bm{A}$ is exactly the column space of $\bm{A}^\top$): $\mathcal{N}(\bm{A}) \bot \mathcal{C}(\bm{A}^\top)$, that is, vectors in the null space of $\bm{A}$ are orthogonal to vectors in the row space of $\bm{A}$. To see this, suppose $\bm{A}$ has rows $\bm{a}_1^\top, \bm{a}_2^\top, \ldots, \bm{a}_m^\top$ and $\bm{A}=[\bm{a}_1^\top; \bm{a}_2^\top; \ldots; \bm{a}_m^\top]$ is the row partition of $\bm{A}$. For any vector $\bm{x}\in \mathcal{N}(\bm{A})$, we have $\bm{A}\bm{x} = \mathbf{0}$, that is, $[\bm{a}_1^\top\bm{x}; \bm{a}_2^\top\bm{x}; \ldots; \bm{a}_m^\top\bm{x}]=\mathbf{0}$. And since the row space of $\bm{A}$ is spanned by $\bm{a}_1^\top, \bm{a}_2^\top, \ldots, \bm{a}_m^\top$. Then $\bm{x}$ is perpendicular to any vectors from $\mathcal{C}(\bm{A}^\top)$ which means $\mathcal{N}(\bm{A}) \bot \mathcal{C}(\bm{A}^\top)$.
	
	Now suppose further that the dimension of row space of $\bm{A}$ is $r$. \textcolor{blue}{Let $\bm{r}_1, \bm{r}_2, \ldots, \bm{r}_r$ be a set of vectors in $\mathbb{R}^n$ and form a basis for the row space of $\bm{A}$}. Then the $r$ vectors $\bm{A}\bm{r}_1, \bm{A}\bm{r}_2, \ldots, \bm{A}\bm{r}_r$ are apparently in the column space of $\bm{A}$,  which are linearly independent. To show this, suppose we have a linear combination of the $r$ vectors: $x_1\bm{A}\bm{r}_1 + x_2\bm{A}\bm{r}_2+ \ldots+ x_r\bm{A}\bm{r}_r=\mathbf{0}$, that is, $\bm{A}(x_1\bm{r}_1 + x_2\bm{r}_2+ \ldots+ x_r\bm{r}_r)=\mathbf{0}$ and the vector $\bm{v}=x_1\bm{r}_1 + x_2\bm{r}_2+ \ldots+ x_r\bm{r}_r$ is in null space of $\bm{A}$: $\bm{v}\in \mathcal{N}(\bm{A})$. But since $\{\bm{r}_1, \bm{r}_2, \ldots, \bm{r}_r\}$ is a basis for the row space of $\bm{A}$, $\bm{v}$ is thus also in the row space of $\bm{A}$ : $\bm{v}\in \mathcal{C}(\bm{A}^\top)$. We have shown above that vectors from null space of $\bm{A}$ is perpendicular to vectors from row space of $\bm{A}$, thus $\bm{v}^\top\bm{v}=0$ and $x_1=x_2=\ldots=x_r=0$. Then \textcolor{blue}{$\bm{A}\bm{r}_1, \bm{A}\bm{r}_2, \ldots, \bm{A}\bm{r}_r$ are in the column space of $\bm{A}$ and they are linearly independent} which means the dimension of the column space of $\bm{A}$ is larger than $r$. This result shows that \textbf{row rank of $\bm{A}\leq $ column rank of $\bm{A}$}. 
	
	If we apply this process again for $\bm{A}^\top$. We will have \textbf{column rank of $\bm{A}\leq $ row rank of $\bm{A}$}. This completes the proof. 
\end{proof}

An important byproduct from the above proof is that if we find a row basis $\{\bm{r}_1, \bm{r}_2, \ldots, \bm{r}_r\}$ of matrix $\bm{A}$ with rank $r$, then, $\{\bm{A}\bm{r}_1, \bm{A}\bm{r}_2, \ldots, \bm{A}\bm{r}_r\}$ is a column basis for it. The reverse is not true normally since $\bm{A}$ may not be invertible. 

However, suppose $\{\bm{c}_1, \bm{c}_2, \ldots, \bm{c}_r\}$ is a column basis for $\bm{A}$, i.e., $\{\bm{c}_1, \bm{c}_2, \ldots, \bm{c}_r\}$ is a row basis for $\bm{A}^\top$. Apply the finding above, it is trivial that $\{\bm{A}^\top\bm{c}_1, \bm{A}^\top\bm{c}_2, \ldots, \bm{A}^\top\bm{c}_r\}$ is a row basis for $\bm{A}$ (i.e., a column basis for $\bm{A}^\top$). 

Specially, when $\bm{A}\in \mathbb{R}^{n\times n}$ is nonsingular and $\{\bm{c}_1, \bm{c}_2, \ldots, \bm{c}_n\}$ is a column basis for $\bm{A}$, then $\{\bm{A}^{-1}\bm{c}_1, \bm{A}^{-1}\bm{c}_2, $ $\ldots, $ $\bm{A}^{-1}\bm{c}_n\}$ is a row basis for it. Or apparently, in this case, the $n$ rows or even the $n$ columns of $\bm{A}$ also form a row basis as well since both the rows and columns span the whole $\mathbb{R}^n$ space .


\subsection{Fundamental Theorem of Linear Algebra}\label{appendix:fundamental-rank-nullity}
The byproduct of the above proof is essential to prove the fundamental theorem of linear algebra. As a recap, for any matrix $\bm{A}\in \mathbb{R}^{m\times n}$, it can be easily verified that any vector in row space of $\bm{A}$ is perpendicular to any vector in null space of $\bm{A}$. Suppose $\bm{x}_n \in \mathcal{N}(\bm{A})$, then $\bm{A}\bm{x}_n = \mathbf{0}$ such that $\bm{x}_n$ is perpendicular to every row of $\bm{A}$ which agrees with our claim. 

Similarly, we can also show that any vector in column space of $\bm{A}$ is perpendicular to any vector in null space of $\bm{A}^\top$. Further, the column space of $\bm{A}$ and the null space of $\bm{A}^\top$ span the whole $\mathbb{R}^m$ 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 shown above. Moreover, when the row space has dimension $r$, the null space has dimension $n-r$. This cannot be easily stated and we prove in the following theorem.

\begin{figure}[h!]
	\centering
	\includegraphics[width=0.98\textwidth]{imgs/lafundamental.pdf}
	\caption{Two pairs of orthogonal subspaces in $\mathbb{R}^n$ and $\mathbb{R}^m$. $\dim(\mathcal{C}(\bm{A}^\top)) + \dim(\mathcal{N}(\bm{A}))=n$ and $\dim(\mathcal{N}(\bm{A}^\top)) + \dim(\mathcal{C}(\bm{A}))=m$. The null space component goes to zero as $\bm{A}\bm{x}_n = \mathbf{0} \in \mathbb{R}^m$. The row space component goes to column space as $\bm{A}\bm{x}_r = \bm{A}(\bm{x}_r+\bm{x}_n)=\bm{b} \in \mathcal{C}(\bm{A})$.}
	\label{fig:lafundamental}
\end{figure}
\begin{mdframed}[hidealllines=true,backgroundcolor=color1]
	\begin{theorem}[Fundamental Theorem of Linear Algebra]\label{theorem:fundamental-linear-algebra}
		
		Orthogonal Complement and Rank-Nullity Theorem: for any matrix $\bm{A}\in \mathbb{R}^{m\times n}$, we have 
		
		$\bullet$ $\mathcal{N}(\bm{A})$ is orthogonal complement to the row space $\mathcal{C}(\bm{A}^\top)$ in $\mathbb{R}^n$: $dim(\mathcal{N}(\bm{A}))+dim(\mathcal{C}(\bm{A}^\top))=n$;
		
		$\bullet$ $\mathcal{N}(\bm{A}^\top)$ is orthogonal complement to the column space $\mathcal{C}(\bm{A})$ in $\mathbb{R}^m$: $dim(\mathcal{N}(\bm{A}^\top))+dim(\mathcal{C}(\bm{A}))=m$;
		
		$\bullet$ For rank-$r$ matrix $\bm{A}$, $dim(\mathcal{C}(\bm{A}^\top)) = dim(\mathcal{C}(\bm{A})) = r$, that is, $dim(\mathcal{N}(\bm{A})) = n-r$ and $dim(\mathcal{N}(\bm{A}^\top))=m-r$.
	\end{theorem}
\end{mdframed}

\begin{proof}[of Theorem~\ref{theorem:fundamental-linear-algebra}]
	Follow from the proof of Theorem~\ref{lemma:equal-dimension-rank}. Let $\bm{r}_1, \bm{r}_2, \ldots, \bm{r}_r$ be a set of vectors in $\mathbb{R}^n$ that form a basis for the row space, then $\bm{A}\bm{r}_1, \bm{A}\bm{r}_2, \ldots, \bm{A}\bm{r}_r$ is a basis for the column space of $\bm{A}$. Let $\bm{n}_1, \bm{n}_2, \ldots, \bm{n}_k \in \mathbb{R}^n$ form a basis for the null space of $\bm{A}$. Follow again from the proof of Theorem~\ref{lemma:equal-dimension-rank}, $\mathcal{N}(\bm{A}) \bot \mathcal{C}(\bm{A}^\top)$, thus, $\bm{r}_1, \bm{r}_2, \ldots, \bm{r}_r$ are perpendicular to $\bm{n}_1, \bm{n}_2, \ldots, \bm{n}_k$. Then, $\{\bm{r}_1, \bm{r}_2, \ldots, \bm{r}_r, \bm{n}_1, \bm{n}_2, \ldots, \bm{n}_k\}$ is linearly independent in $\mathbb{R}^n$.
	
	For any vector $\bm{x}\in \mathbb{R}^n $, $\bm{A}\bm{x}$ is in the column space of $\bm{A}$. Then it can be expressed by a combination of $\bm{A}\bm{r}_1, \bm{A}\bm{r}_2, \ldots, \bm{A}\bm{r}_r$: $\bm{A}\bm{x} = \sum_{i=1}^{r}a_i\bm{A}\bm{r}_i$ which states that $\bm{A}(\bm{x}-\sum_{i=1}^{r}a_i\bm{r}_i) = \mathbf{0}$ and $\bm{x}-\sum_{i=1}^{r}a_i\bm{r}_i$ is thus in $\mathcal{N}(\bm{A})$. Since $\{\bm{n}_1, \bm{n}_2, \ldots, \bm{n}_k\}$ is a basis for the null space of $\bm{A}$, $\bm{x}-\sum_{i=1}^{r}a_i\bm{r}_i$ can be expressed by a combination of $\bm{n}_1, \bm{n}_2, \ldots, \bm{n}_k$: $\bm{x}-\sum_{i=1}^{r}a_i\bm{r}_i = \sum_{j=1}^{k}b_j \bm{n}_j$, i.e., $\bm{x}=\sum_{i=1}^{r}a_i\bm{r}_i + \sum_{j=1}^{k}b_j \bm{n}_j$. That is, any vector $\bm{x}\in \mathbb{R}^n$ can be expressed by $\{\bm{r}_1, \bm{r}_2, \ldots, \bm{r}_r, \bm{n}_1, \bm{n}_2, \ldots, \bm{n}_k\}$ and the set forms a basis for $\mathbb{R}^n$. Thus the dimension sum to $n$: $r+k=n$, i.e., $dim(\mathcal{N}(\bm{A}))+dim(\mathcal{C}(\bm{A}^\top))=n$. Similarly, we can prove $dim(\mathcal{N}(\bm{A}^\top))+dim(\mathcal{C}(\bm{A}))=m$.
\end{proof}

Figure~\ref{fig:lafundamental} demonstrates two pairs of such orthogonal subspaces and shows how $\bm{A}$ takes $\bm{x}$ into the column space. The dimensions of row space of $\bm{A}$ and null space of $\bm{A}$ add to $n$. And the dimensions of column space of $\bm{A}$ and null space of $\bm{A}^\top$ add to $m$. The null space component goes to zero as $\bm{A}\bm{x}_{\bm{n}} = \mathbf{0} \in \mathbb{R}^m$ which is the intersection of column space of $\bm{A}$ and null space of $\bm{A}^\top$. The row space component goes to column space as $\bm{A}\bm{x}_{\bm{r}} = \bm{A}(\bm{x}_{\bm{r}} + \bm{x}_{\bm{n}})=\bm{b}\in \mathbb{R}^m$. 

The fundamental theorem of linear algebra was discussed in \citep{strang1993fundamental}, and a more detailed review is provided in \citep{lu2021revisit} where the authors provide 7 figures from different perspectives (e.g., elementary perspective, least squares, pseudo-inverse and SVD) to describe the theorem.




\section{Gram-Schmidt Way}\label{section:gaussian-way-main}
The UTV decomposition goes further from the QR decomposition which in tern relies on the \textit{Gram-Schmidt process} by factoring the matrix into two orthogonal matrices $\bm{A}=\bm{U}\bm{T}\bm{V}$, where $\bm{U}, \bm{V}$ are orthogonal. The resulting $\bm{T}$ supports rank estimation. The matrix $\bm{T}$ can be lower triangular which results in the ULV decomposition, or it can be upper triangular which results in the URV decomposition. The UTV framework shares similar form as the singular value decomposition (SVD) and can be regarded as inexpensive alternatives to the SVD.

We here firstly formulate the decomposition in the following theorem, and the proof of the existence of the ULV decomposition will be discussed in Section~\ref{section:utv-prove}. \footnote{Notice that original claim for the full ULV decomposition relies on the rank of matrix $\bm{A}$ to be $r$ rather than the column rank \citep{lu2021numerical}. But here we slightly modify the argument since we want to employ it into the proof of the row rank equals to column.}
\begin{mdframed}[hidealllines=true,backgroundcolor=color1]
	\begin{theorem}[Full ULV Decomposition]\label{theorem:ulv-decomposition}
		Every $m\times n$ matrix $\bm{A}$ with \textit{column rank} $r$ can be factored as 
		$$
		\bm{A} = \bm{U} \begin{bmatrix}
			\bm{L} & \mathbf{0} \\
			\mathbf{0} & \mathbf{0} 
		\end{bmatrix}\bm{V},
		$$
		where $\bm{U}\in \mathbb{R}^{m\times m}$ and $\bm{V}\in \mathbb{R}^{n\times n}$ are two orthogonal matrices, and $\bm{L}\in \mathbb{R}^{r\times r}$ is a lower triangular matrix.
	\end{theorem}
\end{mdframed}



From the ULV decomposition, we here provide an alternative way to prove the column rank and row rank of matrix $\bm{A}$ are the same. Note that, in the proof of the QR, LQ and UTV decompositions, we do not utilize the results that the column and row ranks of a matrix are the same. Otherwise, we won't be able to prove it via the existence of the ULV decomposition. 

\begin{proof}[of Theorem~\ref{lemma:equal-dimension-rank}, \textbf{A Second Way}]
	Any $m\times n$ matrix $\bm{A}$ with column rank $r$ can be factored as 
	$$
	\bm{A} = \bm{U}_0 \begin{bmatrix}
		\bm{L} & \mathbf{0} \\
		\mathbf{0} & \mathbf{0} 
	\end{bmatrix}\bm{V}_0,
	$$
	where $\bm{U}_0\in \mathbb{R}^{m\times m}$ and $\bm{V}_0\in \mathbb{R}^{n\times n}$ are two orthogonal matrices, and $\bm{L}\in \mathbb{R}^{r\times r}$ is a lower triangular matrix. Let $\bm{D} = \begin{bmatrix}
		\bm{L} & \mathbf{0} \\
		\mathbf{0} & \mathbf{0} 
	\end{bmatrix}$, the row rank and column rank of $\bm{D}$ are apparently the same. If we could prove the column rank of $\bm{A}$ equals to the column rank of $\bm{D}$, and the row rank of $\bm{A}$ equals to the row rank of $\bm{D}$, then we complete the proof. 
	
	Let $\bm{U} = \bm{U}_0^\top$, $\bm{V}=\bm{V}_0^\top$, then it follows that $\bm{D} = \bm{U}\bm{A}\bm{V}$. Decompose the above idea into two steps, a moment of reflexion reveals that, 
	\begin{itemize}
		\item if we could first prove the row rank and column rank of $\bm{A}$ are equal to those of $\bm{U}\bm{A}$; 
		\item and then, if we further prove the row rank and column rank of $\bm{U}\bm{A} $ are equal to those of $\bm{U}\bm{A}\bm{V}=\bm{D}$, we could also complete the proof.
	\end{itemize}
	
	\paragraph{Row rank and column ranks of $\bm{A}$ are equal to those of $\bm{U}\bm{A}$} Let $\bm{B} = \bm{U}\bm{A}$, and let further $\bm{A}=[\bm{a}_1,\bm{a}_2,\ldots, \bm{a}_n]$ and $\bm{B}=[\bm{b}_1,\bm{b}_2,\ldots,\bm{b}_n]$ be the column partitions of $\bm{A}$ and $\bm{B}$. Therefore, $[\bm{b}_1,\bm{b}_2,\ldots,\bm{b}_n] = [\bm{U}\bm{a}_1,\bm{U}\bm{a}_2,\ldots, \bm{U}\bm{a}_n]$. If $x_1\bm{a}_1+x_2\bm{a}_2+\ldots+x_n\bm{a}_n=0$, then we also obtain 
	$$
	\bm{U}(x_1\bm{a}_1+x_2\bm{a}_2+\ldots+x_n\bm{a}_n) = x_1\bm{b}_1+x_2\bm{b}_2+\ldots+x_n\bm{b}_n = 0.
	$$
	Let $j_1, j_2, \ldots, j_r$ be distinct indices between 1 and $n$, if the set $\{\bm{a}_{j_1}, \bm{a}_{j_2}, \ldots, \bm{a}_{j_r}\}$ is linearly independent, the set $\{\bm{b}_{j_1}, \bm{b}_{j_2}, \ldots, \bm{b}_{j_r}\}$ must also be independent. This implies 
	$$
	dim(\mathcal{C}(\bm{B})) \leq dim(\mathcal{C}(\bm{A})).
	$$
	Similarly, by $\bm{A} = \bm{U}^\top\bm{B}$, we have 
	$$
	dim(\mathcal{C}(\bm{A})) \leq dim(\mathcal{C}(\bm{B})).
	$$
	This implies 
	$$
	dim(\mathcal{C}(\bm{B})) = dim(\mathcal{C}(\bm{A})).
	$$
	Apply the process onto $\bm{B}^\top$ and $\bm{A}^\top$, we have 
	$$
	dim(\mathcal{C}(\bm{B}^\top)) = dim(\mathcal{C}(\bm{A}^\top)).
	$$
	This implies the row rank and column rank of $\bm{A}$ and $\bm{B}=\bm{U}\bm{A}$ are the same.
	Similarly, we can also show that the row rank and column rank of $\bm{U}\bm{A}$ and $\bm{U}\bm{A}\bm{V}$ are the same. This completes the proof.
\end{proof}

\paragraph{Warning on the proof} We might ask: since the UTV framework is an inexpansive alternatives to the SVD, why do not we use the SVD to prove what we want? The answer needs closer scrutiny. The existence of the SVD relies on the fact that the $\bm{A}^\top\bm{A}$ and $\bm{A}$ have same rank which in turn is based on the fundamental theorem of linear algebra that is a byproduct of Theorem~\ref{lemma:equal-dimension-rank} as we have shown in last section. Therefore, this is problematic as we use claim $A$ to prove claim $B$ where $A$ relies on $B$ as well.

\subsection{The Proof of the UTV Decomposition}\label{section:utv-prove}
The most important application of the Gram-Schmidt process is to prove the existence of the QR decomposition, which in turn is essential to prove Theorem~\ref{lemma:equal-dimension-rank}. In this section, we first present the result of the QR decomposition and provide the proof of it via the Gram-Schmidt process, of which other proofs also exist that might be more numerical stable, e.g., via the Householder reflectors and Givens rotations. The detailed discussion can be found in \citep{trefethen1997numerical, golub2013matrix,van2020advanced, lu2021numerical}.  

\subsubsection{QR Decomposition}
In many applications, we are interested in the column space of a matrix $\bm{A}=[\bm{a}_1, \bm{a}_2, ..., \bm{a}_n] \in \mathbb{R}^{m\times n}$. The successive spaces spanned by the columns $\bm{a}_1, \bm{a}_2, \ldots$ of $\bm{A}$ are
$$
\mathcal{C}([\bm{a}_1])\,\,\,\, \subseteq\,\,\,\, \mathcal{C}([\bm{a}_1, \bm{a}_2]) \,\,\,\,\subseteq\,\,\,\, \mathcal{C}([\bm{a}_1, \bm{a}_2, \bm{a}_3])\,\,\,\, \subseteq\,\,\,\, \ldots,
$$
where $\mathcal{C}([\ldots])$ is the subspace spanned by the vectors included in the brackets. The idea of the QR decomposition is the construction of a sequence of orthonormal vectors $\bm{q}_1, \bm{q}_2, \ldots$ that span the same successive subspaces. 
$$
\mathcal{C}([\bm{q}_1])=\mathcal{C}([\bm{a}_1])\,\,\,\, \subseteq\,\,\,\, \mathcal{C}([\bm{q}_1, \bm{q}_2])=\mathcal{C}([\bm{a}_1, \bm{a}_2]) \,\,\,\,\subseteq\,\,\,\, \mathcal{C}([\bm{q}_1, \bm{q}_2, \bm{q}_3])=\mathcal{C}([\bm{a}_1, \bm{a}_2, \bm{a}_3])\,\,\,\, \subseteq\,\,\,\, \ldots,
$$
We provide the result of QR decomposition in the following theorem and we delay the discussion of the existence of it in the next sections.


\begin{mdframed}[hidealllines=true,backgroundcolor=color1]
	\begin{theorem}[QR Decomposition]
		Every $m\times n$ matrix $\bm{A}=[\bm{a}_1, \bm{a}_2, ..., \bm{a}_n]$ with $m\geq n$ can be factored as 
		$$
		\bm{A} = \bm{Q}\bm{R},
		$$
		where 
		
		1. \textbf{Reduced}: $\bm{Q}$ is $m\times n$ with orthonormal columns and $\bm{R}$ is an $n\times n$ upper triangular matrix, which is known as the \textbf{reduced QR decomposition};
		
		2. \textbf{Full}: $\bm{Q}$ is $m\times m$ with orthonormal columns and $\bm{R}$ is an $m\times n$ upper triangular matrix which is known as the \textbf{full QR decomposition}. If further restrict the upper triangular matrix to be a square matrix, the full QR decomposition can be denoted as 
		$$
		\bm{A} = \bm{Q}\begin{bmatrix}
			\bm{R}_0\\
			\mathbf{0}
		\end{bmatrix},
		$$
		where $\bm{R}_0$ is an $m\times m$ upper triangular matrix. 
		
		Specifically, when $\bm{A}$ has full rank, i.e., has independent columns, $\bm{R}$ also has independent columns, and $\bm{R}$ is nonsingular for the reduced case (i.e., with nonzero diagonals).
	\end{theorem}
\end{mdframed}
The QR decomposition can be extended to matrices having dependent columns. In this case, the diagonals of $\bm{R}$ might contain zeros. But for the proof of the UTV decomposition and the Theorem~\ref{append:row-equal-column}, we only discuss the matrix with independent columns (i.e., full column rank).

\subsubsection{Project a Vector Onto Another Vector}\label{section:project-onto-a-vector}
Project a vector $\bm{a}$ to a vector $\bm{b}$ is to find the vector closest to $\bm{a}$ on the line of $\bm{b}$. The projection vector $\hat{\bm{a}}$ is some multiple of $\bm{b}$. Let $\hat{\bm{a}} = \hat{x} \bm{b}$ and $\bm{a}-\hat{\bm{a}}$ is perpendicular to $\bm{b}$ as shown in Figure~\ref{fig:project-line}. We then get the following result:
\begin{mdframed}[hidealllines=true,backgroundcolor=color1,frametitle={Project Vector $\bm{a}$ Onto Vector $\bm{b}$}]
	$\bm{a}-\hat{\bm{a}}$ is perpendicular to $\bm{b}$, so $(\bm{a}-\hat{x}\bm{b})^\top\bm{b}=0$: $\hat{x}$ = $\frac{\bm{a}^\top\bm{b}}{\bm{b}^\top\bm{b}}$ and $\hat{\bm{a}} = \frac{\bm{a}^\top\bm{b}}{\bm{b}^\top\bm{b}}\bm{b} = \frac{\bm{b}\bb^\top}{\bm{b}^\top\bm{b}}\bm{a}$.
\end{mdframed}

\begin{figure}[h!]
	\centering 
	\vspace{-0.35cm}
	\subfigtopskip=2pt
	\subfigbottomskip=2pt
	\subfigcapskip=-5pt
	\subfigure[Project onto a line]{\label{fig:project-line}
		\includegraphics[width=0.47\linewidth]{./imgs/projectline.pdf}}
	\quad 
	\subfigure[Project onto a space]{\label{fig:project-space}
		\includegraphics[width=0.47\linewidth]{./imgs/projectspace.pdf}}
	\caption{Project a vector onto a line and onto a space.}
	\label{fig:projection-qr}
\end{figure}

Further, projecting a vector $\bm{a}$ to a space spanned by $\bm{b}_1, \bm{b}_2, \ldots, \bm{b}_n$ is to find the vector closest to $\bm{a}$ on the column space of $[\bm{b}_1, \bm{b}_2, \ldots, \bm{b}_n]$ can be cast in a similar way. The projection vector $\hat{\bm{a}}$ is a combination of $\bm{b}_1, \bm{b}_2, \ldots, \bm{b}_n$: $\hat{\bm{a}} = \hat{x}_1\bm{b}_1+ \hat{x}_2\bm{b}_2+\ldots+\hat{x}_n\bm{b}_n$. This is actually a least squares problem. To find the projection, we just solve the normal equation $\bm{B}^\top\bm{B}\hat{\bm{x}} = \bm{B}^\top\bm{a}$ where $\bm{B}=[\bm{b}_1, \bm{b}_2, \ldots, \bm{b}_n]$ and $\hat{\bm{x}}=[\hat{x}_1, \hat{x}_2, \ldots, \hat{x}_n]$. We refer the details of this section to \citep{strang1993introduction, trefethen1997numerical, golub2013matrix, lu2021rigorous} as it is not the main interest of this paper.


\subsubsection{Existence of the QR Decomposition via the Gram-Schmidt Process}\label{section:gram-schmidt-process}
For three independent vectors $\bm{a}_1, \bm{a}_2, \bm{a}_3$ and the space spanned by the three independent vectors $\mathcal{C}{([\bm{a}_1, \bm{a}_2, \bm{a}_3])}$, i.e., the column space of matrix $[\bm{a}_1, \bm{a}_2, \bm{a}_3]$. We intend to construct three orthogonal vectors $\bm{b}_1, \bm{b}_2, \bm{b}_3$ in which case $\mathcal{C}{([\bm{b}_1, \bm{b}_2, \bm{b}_3])}$ = $\mathcal{C}{([\bm{a}_1, \bm{a}_2, \bm{a}_3])}$. Then we divide the orthogonal vectors by their length to normalize. This process produces three orthonormal vectors $\bm{q}_1 = \frac{\bm{b}_1}{||\bm{b}_1||}$, $\bm{q}_2 = \frac{\bm{b}_2}{||\bm{b}_2||}$, $\bm{q}_2 = \frac{\bm{b}_2}{||\bm{b}_2||}$.

For the first vector, we choose $\bm{b}_1 = \bm{a}_1$ directly. The second vector $\bm{b}_1$ must be perpendicular to the first one. This is actually the vector $\bm{a}_2$ subtracting its projection along $\bm{b}_1$:
\begin{equation}
	\begin{aligned}
		\bm{b}_2 &= \bm{a}_2- \frac{\bm{b}_1 \bm{b}_1^\top}{\bm{b}_1^\top\bm{b}_1} \bm{a}_2 = (\bm{I}- \frac{\bm{b}_1 \bm{b}_1^\top}{\bm{b}_1^\top\bm{b}_1} )\bm{a}_2   \qquad &(\text{Projection view})\\
		&= \bm{a}_2-  \underbrace{\frac{ \bm{b}_1^\top \bm{a}_2}{\bm{b}_1^\top\bm{b}_1} \bm{b}_1}_{\hat{\bm{a}}_2}, \qquad &(\text{Combination view}) \nonumber
	\end{aligned}
\end{equation}
where the first equation shows $\bm{b}_2$ is a multiplication of a matrix $(\bm{I}- \frac{\bm{b}_1 \bm{b}_1^\top}{\bm{b}_1^\top\bm{b}_1} )$ and $\bm{a}_2$, i.e., project $\bm{a}_2$ onto the orthogonal complement space of $\mathcal{C}{([\bm{b}_1])}$. The second equation shows $\bm{a}_2$ is a combination of $\bm{b}_1$ and $\bm{b}_2$.
Clearly, the space spanned by $\bm{b}_1, \bm{b}_2$ is the same space spanned by $\bm{a}_1, \bm{a}_2$. The siguation is shown in Figure~\ref{fig:gram-schmidt1} in which we choose \textit{the direction of $\bm{b}_1$ as the $x$-axis in the Cartesian coordinate system}. $\hat{\bm{a}}_2$ is the projection of $\bm{a}_2$ onto the line $\bm{b}_1$. It can be clearly shown that the part of $\bm{a}_2$ perpendicular to $\bm{b}_1$ is $\bm{b}_2 = \bm{a}_2 - \hat{\bm{a}}_2$ from the figure.


For the third vector $\bm{b}_3$, it must be perpendicular to both the $\bm{b}_1$ and $\bm{b}_2$ which is actually the vector $\bm{a}_3$ subtracting its projection along the plane spanned by $\bm{b}_1$ and $\bm{b}_2$
\begin{equation}\label{equation:gram-schdt-eq2}
	\begin{aligned}
		\bm{b}_3 &= \bm{a}_3- \frac{\bm{b}_1 \bm{b}_1^\top}{\bm{b}_1^\top\bm{b}_1} \bm{a}_3 - \frac{\bm{b}_2 \bm{b}_2^\top}{\bm{b}_2^\top\bm{b}_2} \bm{a}_3 = (\bm{I}- \frac{\bm{b}_1 \bm{b}_1^\top}{\bm{b}_1^\top\bm{b}_1}  - \frac{\bm{b}_2 \bm{b}_2^\top}{\bm{b}_2^\top\bm{b}_2} )\bm{a}_3   \qquad &(\text{Projection view})\\
		&= \bm{a}_3- \underbrace{\frac{ \bm{b}_1^\top\bm{a}_3}{\bm{b}_1^\top\bm{b}_1} \bm{b}_1}_{\hat{\bm{a}}_3} - \underbrace{\frac{ \bm{b}_2^\top\bm{a}_3}{\bm{b}_2^\top\bm{b}_2}  \bm{b}_2}_{\bar{\bm{a}}_3},    \qquad &(\text{Combination view})
	\end{aligned}
\end{equation}
where the first equation shows $\bm{b}_3$ is a multiplication of a matrix $(\bm{I}- \frac{\bm{b}_1 \bm{b}_1^\top}{\bm{b}_1^\top\bm{b}_1}  - \frac{\bm{b}_2 \bm{b}_2^\top}{\bm{b}_2^\top\bm{b}_2} )$ and $\bm{a}_3$, i.e., project $\bm{a}_3$ onto the orthogonal complement space of $\mathcal{C}{([\bm{b}_1, \bm{b}_2])}$. The second equation shows $\bm{a}_3$ is a combination of $\{\bm{b}_1, \bm{b}_2, \bm{b}_3\}$. We will see this property is essential in the idea of the QR decomposition.
Again, it can be shown that the space spanned by $\{\bm{b}_1, \bm{b}_2, \bm{b}_3\}$ is the same space spanned by $\{\bm{a}_1, \bm{a}_2, \bm{a}_3\}$. The situation is shown in Figure~\ref{fig:gram-schmidt2}, in which we choose \textit{the direction of $\bm{b}_2$ as the $y$-axis of the Cartesian coordinate system}. $\hat{\bm{a}}_3$ is the projection of $\bm{a}_3$ onto the line $\bm{b}_1$, $\bar{\bm{a}}_3$ is the projection of $\bm{a}_3$ onto the line $\bm{b}_2$. It can be shown that the part of $\bm{a}_3$ perpendicular to both $\bm{b}_1$ and $\bm{b}_2$ is $\bm{b}_3=\bm{a}_3-\hat{\bm{a}}_3-\bar{\bm{a}}_3$ from the figure.


Finally, we normalize each vector by dividing their length which produces three orthonormal vectors $\bm{q}_1 = \frac{\bm{b}_1}{||\bm{b}_1||}$, $\bm{q}_2 = \frac{\bm{b}_2}{||\bm{b}_2||}$, $\bm{q}_2 = \frac{\bm{b}_2}{||\bm{b}_2||}$.


\begin{figure}[H]
	\centering 
	\vspace{-0.35cm}
	\subfigtopskip=2pt
	\subfigbottomskip=2pt
	\subfigcapskip=-5pt
	\subfigure[Project $\bm{a}_2$ onto the space perpendicular to $\bm{b}_1$.]{\label{fig:gram-schmidt1}
		\includegraphics[width=0.47\linewidth]{./imgs/gram-schmidt1.pdf}}
	\quad 
	\subfigure[Project $\bm{a}_3$ onto the space perpendicular to $\bm{b}_1, \bm{b}_2$.]{\label{fig:gram-schmidt2}
		\includegraphics[width=0.47\linewidth]{./imgs/gram-schmidt2.pdf}}
	\caption{Gram-Schmidt process.}
	\label{fig:gram-schmidt-12}
\end{figure}

This idea can be extended to a set of vectors rather than only three. And we call this process as \textit{Gram-Schmidt process}. After this process, matrix $\bm{A}$ will be triangularized. 

As we mentioned previously, the idea of the QR decomposition is the construction of a sequence of orthonormal vectors $\bm{q}_1, \bm{q}_2, \ldots$ that span the same successive subspaces. 
$$
\mathcal{C}([\bm{q}_1])=\mathcal{C}([\bm{a}_1])\,\,\,\, \subseteq\,\,\,\, \mathcal{C}([\bm{q}_1, \bm{q}_2])=\mathcal{C}([\bm{a}_1, \bm{a}_2]) \,\,\,\,\subseteq\,\,\,\, \mathcal{C}([\bm{q}_1, \bm{q}_2, \bm{q}_3])=\mathcal{C}([\bm{a}_1, \bm{a}_2, \bm{a}_3])\,\,\,\, \subseteq\,\,\,\, \ldots,
$$
This implies any $\bm{a}_k$ is in the space spanned by $\mathcal{C}([\bm{q}_1, \bm{q}_2, \ldots, \bm{q}_k])$. \footnote{And also, any $\bm{q}_k$ is in the space spanned by $\mathcal{C}([\bm{a}_1, \bm{a}_2, \ldots, \bm{a}_k])$.} As long as we have found these orthonormal vectors, to reconstruct $\bm{a}_i$'s from the orthonormal matrix $\bm{Q}=[\bm{q}_1, \bm{q}_2, \ldots, \bm{q}_n]$, an upper triangular matrix $\bm{R}$ is needed such that $\bm{A} = \bm{Q}\bm{R}$.


A full QR decomposition of an $m\times n$ matrix with independent columns goes further by appending additional $m-n$ orthonormal columns to $\bm{Q}$ so that it becomes an $m\times m$ orthogonal matrix. In addition, rows of zeros are appended to $\bm{R}$ so that it becomes an $m\times n$ upper triangular matrix. We call the additional columns in $\bm{Q}$ as \textbf{silent columns} and additional rows in $\bm{R}$ as \textbf{silent rows}. The comparison of the reduced QR decomposition and the full QR decomposition is shown in Figure~\ref{fig:qr-comparison} where silent columns in $\bm{Q}$ are denoted in grey, blank entries are zero and blue entries are elements that are not necessarily zero.

\begin{figure}[H]
	\centering 
	\vspace{-0.35cm}
	\subfigtopskip=2pt
	\subfigbottomskip=2pt
	\subfigcapskip=-5pt
	\subfigure[Reduced QR decomposition]{\label{fig:gphalf}
		\includegraphics[width=0.47\linewidth]{./imgs/qrreduced.pdf}}
	\quad 
	\subfigure[Full QR decomposition]{\label{fig:gpall}
		\includegraphics[width=0.47\linewidth]{./imgs/qrfull.pdf}}
	\caption{Comparison of reduced and full QR decomposition.}
	\label{fig:qr-comparison}
\end{figure}

\subsubsection{LQ Decomposition}
We previously proved the existence of the QR decomposition via the Gram-Schmidt process in which case we are interested in the column space of a matrix $\bm{A}=[\bm{a}_1, \bm{a}_2, ..., \bm{a}_n] \in \mathbb{R}^{m\times n}$. 
However, in many applications, we are also interested in the row space of a matrix $\bm{B}=[\bm{b}_1^\top; \bm{b}_2^\top; ...;\bm{b}_m^\top] \in \mathbb{R}^{m\times n}$, where $\bm{b}_i$ is the $i$-th row of $\bm{B}$ \citep{tanaka2003stochastic, schilders2009solution}. The successive spaces spanned by the rows $\bm{b}_1, \bm{b}_2, \ldots$ of $\bm{B}$ are
$$
\mathcal{C}([\bm{b}_1])\,\,\,\, \subseteq\,\,\,\, \mathcal{C}([\bm{b}_1, \bm{b}_2]) \,\,\,\,\subseteq\,\,\,\, \mathcal{C}([\bm{b}_1, \bm{b}_2, \bm{b}_3])\,\,\,\, \subseteq\,\,\,\, \ldots,
$$
By applying QR decomposition on $\bm{B}^\top = \bm{Q}_0\bm{R}$, we recover the LQ decomposition of the matrix $\bm{B} = \bm{L} \bm{Q}$ where $\bm{Q} = \bm{Q}_0^\top$ and $\bm{L} = \bm{R}^\top$.





\subsubsection{UTV Decomposition: ULV and URV Decomposition}\label{section:ulv-urv-decomposition}

Finally, we come to the proof of the ULV decomposition. 
The existence of the ULV decomposition is from both the QR and LQ decomposition.
\begin{proof}[of Theorem~\ref{theorem:ulv-decomposition}]
	For any rank $r$ matrix $\bm{A}=[\bm{a}_1, \bm{a}_2, \ldots, \bm{a}_n]$, we can use a column permutation matrix $\bm{P}$ such that the independent columns of $\bm{A}$ appear in the first $r$ columns of $\bm{A}\bm{P}$. Without loss of generality, we assume $\bm{b}_1, \bm{b}_2, \ldots, \bm{b}_r$ are the $r$ independent columns of $\bm{A}$ and 
	$$
	\bm{A}\bm{P} = [\bm{b}_1, \bm{b}_2, \ldots, \bm{b}_r, \bm{b}_{r+1}, \ldots, \bm{b}_n].
	$$
	Let $\bm{Z} = [\bm{b}_1, \bm{b}_2, \ldots, \bm{b}_r] \in \mathbb{R}^{m\times r}$. Since any $\bm{b}_i$ is in the column space of $\bm{Z}$, we can find a matrix $\bm{E}\in \mathbb{R}^{r\times (n-r)}$ such that 
	$$
	[\bm{b}_{r+1}, \bm{b}_{r+2}, \ldots, \bm{b}_n] = \bm{Z} \bm{E}.
	$$
	That is, 
	$$
	\bm{A}\bm{P} = [\bm{b}_1, \bm{b}_2, \ldots, \bm{b}_r, \bm{b}_{r+1}, \ldots, \bm{b}_n] = \bm{Z}
	\begin{bmatrix}
		\bm{I}_r & \bm{E}
	\end{bmatrix},
	$$
	where $\bm{I}_r$ is an $r\times r$ identity matrix. Moreover, $\bm{Z}\in \mathbb{R}^{m\times r}$ has full column rank such that its full QR decomposition is given by $\bm{Z} = \bm{U}\begin{bmatrix}
		\bm{R} \\
		\mathbf{0}
	\end{bmatrix} \in \mathbb{R}^{m\times r}$, where $\bm{R}\in \mathbb{R}^{r\times r}$ is an upper triangular matrix with full column rank and full row rank (because of the special structure of $\bm{R}$) and $\bm{U}$ is an orthogonal matrix. This implies 
	\begin{equation}\label{equation:ulv-smpl}
		\bm{A}\bm{P} = \bm{Z}
		\begin{bmatrix}
			\bm{I}_r & \bm{E}
		\end{bmatrix}
		=
		\bm{U}\begin{bmatrix}
			\bm{R} \\
			\mathbf{0}
		\end{bmatrix}
		\begin{bmatrix}
			\bm{I}_r & \bm{E}
		\end{bmatrix}
		=
		\bm{U}\begin{bmatrix}
			\bm{R} & \bm{R}\bm{E} \\
			\mathbf{0} & \mathbf{0} 
		\end{bmatrix}.
	\end{equation}
	Since $\bm{R}$ has full row rank, this means 
	$\begin{bmatrix}
		\bm{R} & \bm{R}\bm{E} 
	\end{bmatrix}$ also has full row rank such that its full LQ decomposition is given by 
	$\begin{bmatrix}
		\bm{L} & \mathbf{0} 
	\end{bmatrix} \bm{V}_0$ where $\bm{L}\in \mathbb{R}^{r\times r}$ is a lower triangular matrix and $\bm{V}_0$ is an orthogonal matrix. Substitute into Equation~\eqref{equation:ulv-smpl}, we have 
	$$
	\bm{A} = \bm{U} \begin{bmatrix}
		\bm{L} & \mathbf{0} \\
		\mathbf{0} & \mathbf{0} 
	\end{bmatrix}\bm{V}_0 \bm{P}^{-1}.
	$$
	Let $\bm{V} =\bm{V}_0 \bm{P}^{-1}$ which is a product of two orthogonal matrices, and therefore is also an orthogonal matrix. This completes the proof.
\end{proof}

Suppose the ULV decomposition of matrix $\bm{A}$ is 
$$
\bm{A} = \bm{U} \begin{bmatrix}
	\bm{L} & \mathbf{0} \\
	\mathbf{0} & \mathbf{0} 
\end{bmatrix}\bm{V}.
$$
Let $\bm{U}_0 = \bm{U}_{:,1:r}$ and $\bm{V}_0 = \bm{V}_{1:r,:}$, i.e., $\bm{U}_0$ contains only the first $r$ columns of $\bm{U}$, and $\bm{V}_0$ contains only the first $r$ rows of $\bm{V}$. Then, we still have $\bm{A} = \bm{U}_0 \bm{L}\bm{V}_0$. This is known as the \textbf{reduced ULV decomposition}.
The comparison between the reduced and the full ULV decomposition is shown in Figure~\ref{fig:ulv-comparison} where white entries are zero and blue entries are not necessarily zero.
\begin{figure}[H]
	\centering 
	\vspace{-0.35cm}
	\subfigtopskip=2pt
	\subfigbottomskip=2pt
	\subfigcapskip=-5pt
	\subfigure[Reduced ULV decomposition]{\label{fig:ulvhalf}
		\includegraphics[width=0.47\linewidth]{./imgs/ulvreduced.pdf}}
	\quad 
	\subfigure[Full ULV decomposition]{\label{fig:ulvall}
		\includegraphics[width=0.47\linewidth]{./imgs/ulvfull.pdf}}
	\caption{Comparison of reduced and full ULV}
	\label{fig:ulv-comparison}
\end{figure}

Similarly, we can also claim the URV decomposition as follows.
\begin{mdframed}[hidealllines=true,backgroundcolor=color1]
	\begin{theorem}[Full URV Decomposition]\label{theorem:urv-decomposition}
		Every $m\times n$ matrix $\bm{A}$ with rank $r$ can be factored as 
		$$
		\bm{A} = \bm{U} \begin{bmatrix}
			\bm{R} & \mathbf{0} \\
			\mathbf{0} & \mathbf{0} 
		\end{bmatrix}\bm{V},
		$$
		where $\bm{U}\in \mathbb{R}^{m\times m}$ and $\bm{V}\in \mathbb{R}^{n\times n}$ are two orthogonal matrices, and $\bm{R}\in \mathbb{R}^{r\times r}$ is an upper triangular matrix.
	\end{theorem}
\end{mdframed}
	The proof is similar to that of ULV, except this time, we need a row permutation rather than a column permutation. A detailed discussion can be found in \citep{lu2021numerical}.


Again, there is a version of reduced URV decomposition and the difference between the full and reduced URV can be implied from the context as shown in Figure~\ref{fig:ulv-comparison}. The ULV and URV sometimes are referred to as the UTV decomposition framework \citep{fierro1997low, golub2013matrix}.

















\section{Gaussian Elimination Way}

CR decomposition is recently proposed in \citep{strang2021every, stranglu} that is a direct product of Gaussian elimination where the \textit{elementary transformations} will not change the rank of matrices. We firstly give the result and we will discuss the existence and the origin of this decomposition in the following paragraphs.
\begin{mdframed}[hidealllines=true,backgroundcolor=color1]
	\begin{theorem}[CR Decomposition]\label{theorem:cr-decomposition}
		Any rank-$r$ matrix $\bm{A} \in \mathbb{R}^{m \times n}$ 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 n$ matrix to reconstruct the columns of $\bm{A}$ from columns of $\bm{C}$. In particular, $\bm{R}$ is the row reduced echelon form (RREF) of $\bm{A}$ without the zero rows.
		
		The storage for the decomposition is then reduced or potentially increased from $mn$ to $r(m+n)$.
	\end{theorem}
\end{mdframed}


In short, we first compute the row reduced echelon form of matrix $\bm{A}$ by $rref(\bm{A})$, Then $\bm{C}$ is obtained by removing from $\bm{A}$ all non-pivot columns (which can be determined by looking for columns in $rref(\bm{A})$ which do not contain a pivot). And $\bm{R}$ is obtained by eliminating zero rows of $rref(\bm{A})$. And this is actually a special case of \textbf{rank decomposition} of matrix $\bm{A}$. However, CR decomposition is so special that it involves in the row reduced echelon form.

$\bm{R}$ has a remarkable form whose $r$ columns containing the pivots form an $r\times r$ identity matrix. Note again that we can just remove the zero rows from the row reduced echelon form to obtain this matrix $\bm{R}$. In \citep{strang2021every}, the authors give a specific notation for the row reduced echelon form without removing the zero rows as $\bm{R}_0$:
$$
\bm{R}_0 = rref(\bm{A})=
\begin{bmatrix}
	\bm{R} \\
	\mathbf{0}
\end{bmatrix}=
\begin{bmatrix}
	\bm{I}_r & \bm{F} \\
	\mathbf{0} & \mathbf{0}
\end{bmatrix}\bm{P}, \footnote{Permutation matrix $\bm{P}$ on the right side of a matrix is to permute the columns of that matrix. 
}
$$
where the $n\times n$ permutation matrix $\bm{P}$ puts the columns of $r\times r$ identity matrix $\bm{I}_r$ into the correct positions, matching the first $r$ independent columns of the original matrix $\bm{A}$.

The CR decomposition also reveals the great theorem of linear algebra that the row rank equals the column rank of any matrix. Thus we call it a \textit{Gaussian elimination} way.

\begin{proof}[of Theorem~\ref{lemma:equal-dimension-rank}, \textbf{The Third Way}]
	For CR decomposition of matrix $\bm{A}=\bm{C}\bm{R}$, we have $\bm{R} = [\bm{I}_r, \bm{F} ]\bm{P}$, where $\bm{P}$ is an $n\times n$ permutation to put the columns of the $r\times r$ identity matrix $\bm{I}_r$ into the correct positions as shown above. It can be easily verified that the $r$ rows of $\bm{R}$ are independent from the submatrix of $\bm{I}_r$ (since $\bm{I}_r$ is nonsingular) such that the row rank of $\bm{R}$ is $r$. 
	
	Firstly, from the definition of CR decomposition, the $r$ columns of $\bm{C}$ are from $r$ independent columns of $\bm{A}$, the column rank of $\bm{A}$ is $r$. Further, 
	
	$\bullet$ Since $\bm{A}=\bm{C}\bm{R}$, all rows of $\bm{A}$ are combinations of the rows of $\bm{R}$. That is, the row rank of $\bm{A}$ is no larger than the row rank of $\bm{R}$;
	
	$\bullet$ From $\bm{A}=\bm{C}\bm{R}$, we also have $(\bm{C}^\top\bm{C})^{-1}\bm{C}^\top\bm{C}\bm{R} = (\bm{C}^\top\bm{C})^{-1}\bm{C}^\top\bm{A}$, that is $\bm{R} = (\bm{C}^\top\bm{C})^{-1}\bm{C}^\top\bm{A}$. $\bm{C}^\top\bm{C}$ is nonsingular since $\bm{C}$ has full column rank $r$. Then all rows of $\bm{R}$ are also combinations of the rows of $\bm{A}$. That is, the row rank of $\bm{R}$ is no larger than the row rank of $\bm{A}$;
	
	$\bullet$ By ``sandwiching", the row rank of $\bm{A}$ is equal to the row rank of $\bm{R}$ which is $r$.
	
	Therefore, both the row rank and column rank of of $\bm{A}$ are equal to $r$ from which the result follows.
\end{proof}



\subsection{Rank Decomposition}
We previously mentioned that the CR decomposition is a special case of rank decomposition. Formally, we prove the existence of the rank decomposition rigorously in the following theorem.

\begin{mdframed}[hidealllines=true,backgroundcolor=color1]
	\begin{theorem}[Rank Decomposition]\label{theorem:rank-decomposition}
		Any rank-$r$ matrix $\bm{A} \in \mathbb{R}^{m \times n}$ can be factored as 
		$$
		\bm{A} = \bm{D} \bm{F}
		$$
		where $\bm{D} \in \mathbb{R}^{m\times r}$ has rank $r$, and $\bm{F} \in \mathbb{R}^{r\times n}$ also has rank $r$, i.e., $\bm{D},\bm{F}$ have full rank $r$.
		
		The storage for the decomposition is then reduced or potentially increased from $mn$ to $r(m+n)$.
	\end{theorem}
\end{mdframed}
\begin{proof}[of Theorem~\ref{theorem:rank-decomposition}]
	By ULV decomposition in Theorem~\ref{theorem:ulv-decomposition}, we can decompose $\bm{A}$ by 
	$$
	\bm{A} = \bm{U} \begin{bmatrix}
		\bm{L} & \mathbf{0} \\
		\mathbf{0} & \mathbf{0} 
	\end{bmatrix}\bm{V}.
	$$
	Let $\bm{U}_0 = \bm{U}_{:,1:r}$ and $\bm{V}_0 = \bm{V}_{1:r,:}$, i.e., $\bm{U}_0$ contains only the first $r$ columns of $\bm{U}$, and $\bm{V}_0$ contains only the first $r$ rows of $\bm{V}$. Then, we still have $\bm{A} = \bm{U}_0 \bm{L}\bm{V}_0$ where $\bm{U}_0 \in \mathbb{R}^{m\times r}$ and $\bm{V}_0\in \mathbb{R}^{r\times n}$. This is also known as the reduced ULV decomposition as shown in Figure~\ref{fig:ulv-comparison}. Let \{$\bm{D} = \bm{U}_0\bm{L}$ and $\bm{F} =\bm{V}_0$\}, or \{$\bm{D} = \bm{U}_0$ and $\bm{F} =\bm{L}\bm{V}_0$\}, we find such rank decomposition.
\end{proof}
The rank decomposition is not unique. Even by elementary transformations, we have 
$$
\bm{A} = 
\bm{E}_1
\begin{bmatrix}
	\bm{Z} & \mathbf{0} \\
	\mathbf{0} & \mathbf{0} 
\end{bmatrix}
\bm{E}_2,
$$
where $\bm{E}_1 \in \mathbb{R}^{m\times m}, \bm{E}_2\in \mathbb{R}^{n\times n}$ represent elementary row and column operations, $\bm{Z}\in \mathbb{R}^{r\times r}$. The transformation is rather general, and there are dozens of these $\bm{E}_1,\bm{E}_2,\bm{Z}$ matrices. Similar construction on this decomposition as shown in the above proof, we can recover another rank decomposition. 

Analogously, we can find such $\bm{D},\bm{F}$ by SVD, URV, CR, Skeleton and many other factorization algorithms. However, we may connect the different rank decompositions by the following lemma.
\begin{mdframed}[hidealllines=true,backgroundcolor=color1]
	\begin{lemma}[Connection Between Rank Decompositions]\label{lemma:connection-rank-decom}
		For any two rank decompositions of $\bm{A}=\bm{D}_1\bm{F}_1=\bm{D}_2\bm{F}_2$, there exists a nonsingular matrix $\bm{P}$ such that 
		$$
		\bm{D}_1 = \bm{D}_2\bm{P}
		\qquad
		\text{and}
		\qquad 
		\bm{F}_1 = \bm{P}^{-1}\bm{F}_2.
		$$
	\end{lemma}
\end{mdframed}
\begin{proof}[of Lemma~\ref{lemma:connection-rank-decom}]
	Since $\bm{D}_1\bm{F}_1=\bm{D}_2\bm{F}_2$, we have $\bm{D}_1\bm{F}_1\bm{F}_1^\top=\bm{D}_2\bm{F}_2\bm{F}_1^\top$. It is trivial that $rank(\bm{F}_1\bm{F}_1^\top)=rank(\bm{F}_1)=r$ such that $\bm{F}_1\bm{F}_1^\top$ is a square matrix with full rank and thus is nonsingular. This implies $\bm{D}_1=\bm{D}_2\bm{F}_2\bm{F}_1^\top(\bm{F}_1\bm{F}_1^\top)^{-1}$. Let $\bm{P}=\bm{F}_2\bm{F}_1^\top(\bm{F}_1\bm{F}_1^\top)^{-1}$, we have $\bm{D}_1=\bm{D}_2\bm{P}$ and $\bm{F}_1 = \bm{P}^{-1}\bm{F}_2$. 
\end{proof}



\subsection{Beyond UTV Decomposition}
We have shown that the UTV decomposition can be utilized to prove that the row and column ranks of a matrix are equal. From a basic course of linear algebra, the Gaussian elimination can results in the decomposition
$$
\bm{A} = \bm{E}_1 \begin{bmatrix}
	\bm{I}_r & \mathbf{0} \\
	\mathbf{0} & \mathbf{0} 
\end{bmatrix}\bm{E}_2,
$$
where $\bm{E}_1, \bm{E}_2$ are elementary transformations. By same argument as in Section~\ref{section:gaussian-way-main}, we can also find the same proof for Theorem~\ref{lemma:equal-dimension-rank}. 

Alternatively, we recall that the elementary row or column operations do not
alter the row rank or the column rank of $\bm{A}$. Using these elementary transformations $\bm{E}_1, \bm{E}_2$, we will find the row and column ranks of $\bm{A}$ are equal to those of $\begin{bmatrix}
	\bm{I}_r & \mathbf{0} \\
	\mathbf{0} & \mathbf{0} 
\end{bmatrix}$ which proves the result as well.



\section{Skeleton/CUR Decomposition}
In Theorem~\ref{lemma:equal-dimension-rank}, we proved the row rank and the column rank of a matrix are equal. 
An elementary decomposition that is highly related to this theorem is called the skeleton decomposition.


\begin{mdframed}[hidealllines=true,backgroundcolor=color1]
	\begin{theorem}[Skeleton Decomposition]\label{theorem:skeleton-decomposition}
		Any rank-$r$ matrix $\bm{A} \in \mathbb{R}^{m \times n}$ can be factored as 
		$$
		\bm{A} = \bm{C} \bm{U}^{-1} \bm{R},
		$$
		where $\bm{C}$ is some $r$ independent columns of $\bm{A}$, $\bm{R}$ is some $r$ independent rows of $\bm{A}$ and $\bm{U}\in \mathbb{R}^{r\times r}$ is the nonsingular submatrix on the intersection. 
		
	
	\end{theorem}
\end{mdframed}

Skeleton decomposition is also known as \textit{CUR decomposition}. The illustration of skeleton decomposition is shown in Figure~\ref{fig:skeleton}. Specifically, if $I,J$ are the indices of rows and columns selected from $\bm{A}$ into $\bm{R}$ and $\bm{C}$ respectively, $\bm{U}$ can be denoted as $\bm{U}=\bm{A}[I,J]$.
\begin{figure}[H]
	\centering
	\includegraphics[width=0.7\textwidth]{imgs/skeleton.pdf}
	\caption{Demonstration of skeleton decomposition of a matrix}
	\label{fig:skeleton}
\end{figure}

We have shown in previous sections that the Theorem~\ref{lemma:equal-dimension-rank} can be proved from Gram-Schmidt process or Gaussian elimination perspectives. The claim from Theorem~\ref{lemma:equal-dimension-rank} is also essential to prove the existence of skeleton decomposition. A moment of reflexion would reveal that Gram-Schmidt process or Gaussian elimination in turn can be utilized to produce such $\bm{C}, \bm{U}, \bm{R}$ matrices for this decomposition (a detailed discussion is provided in \citep{lu2021numerical}).


We now prove the existence of the skeleton decomposition and the proof is rather elementary. 
\begin{proof}[of Theorem~\ref{theorem:skeleton-decomposition}]
	The proof relies on the existence of such nonsingular matrix $\bm{U}$ which is central to this decomposition method. 
	
	\paragraph{Existence of such nonsingular matrix $\bm{U}$} Since matrix $\bm{A}$ is rank-$r$, we can pick $r$ columns from $\bm{A}$ so that they are linearly independent. Suppose we put the specific $r$ independent columns $\bm{a}_{i1}, \bm{a}_{i2}, \ldots, \bm{a}_{ir}$ into columns of an $m\times r$ matrix $\bm{N}=[\bm{a}_{i1}, \bm{a}_{i2}, \ldots, \bm{a}_{ir}] \in \mathbb{R}^{m\times r}$. The dimension of column space of $\bm{N}$ is $r$ so that the dimension of row space of $\bm{N}$ is also $r$ by Theorem~\ref{lemma:equal-dimension-rank}. Again, we can pick $r$ independent rows $\bm{n}_{j1}^\top,\bm{n}_{j2}^\top, \ldots, \bm{n}_{jr}^\top $ from $\bm{N}$ and put the specific $r$ rows into rows of a $r\times r$ matrix $\bm{U} = [\bm{n}_{j1}^\top; \bm{n}_{j2}^\top; \ldots; \bm{n}_{jr}^\top]\in \mathbb{R}^{r\times r}$. Using Theorem~\ref{lemma:equal-dimension-rank} again, the dimension of the column space of $\bm{U}$ is also $r$ which means there are the $r$ independent columns from $\bm{U}$. So $\bm{U}$ is such a nonsingular matrix with size $r\times r$.
	
	As long as we find the nonsingular $r\times r$ matrix $\bm{U}$ inside $\bm{A}$, we can find the existence of the skeleton decomposition as follows.
	
	Since $\bm{U}$ is a nonsingular matrix, the columns of $\bm{U}$ are linearly independent. Thus the columns of matrix $\bm{C}$ based on columns of $\bm{U}$ are also linearly independent (i.e., select the $r$ columns of $\bm{A}$ with same entries of the $\bm{U}$ matrix. Here $\bm{C}$ is equal to the $\bm{N}$ we construct above). 
	
	As the rank of matrix $\bm{A}$ is $r$, if we take any other column $\bm{a}_i$ of $\bm{A}$, $\bm{a}_i$ can be represented as a linear combination of the columns of $\bm{C}$, i.e., there exists a vector $\bm{x}$ such that $\bm{a}_i = \bm{C} \bm{x}$, for all $ i\in \{1, 2, \ldots, n\}$. Let $r$ rows of $\bm{a}_i$ corresponding to the row entries of $\bm{U}$ be $\bm{r}_i \in \mathbb{R}^r$ for all $i\in \{1, 2, \ldots, n\}$ (i.e., $\bm{r}_i$ contains $r$ entries of $\bm{a}_i$). That is, select the $r$ entries of $\bm{a}_i$'s corresponding to the entries of $\bm{U}$ as follows:
	$$
	\bm{A} = [\bm{a}_1,\bm{a}_2, \ldots, \bm{a}_n]\in \mathbb{R}^{m\times n} \qquad \longrightarrow \qquad
	[\bm{r}_1, \bm{r}_2, \ldots, \bm{r}_n] \in \mathbb{R}^{r\times n}.
	$$
	Since $\bm{a}_i = \bm{C}\bm{x}$, $\bm{U}$ is a submatrix inside $\bm{C}$, and $\bm{r}_i$ is a subvector inside $\bm{a}_i$, we have $\bm{r}_i = \bm{U} \bm{x}$ which is equivalent to $\bm{x} = \bm{U}^{-1} \bm{r}_i$. Thus for every $i$, we have $\bm{a}_i = \bm{C} \bm{U}^{-1} \bm{r}_i$. Combine the $n$ columns of such $\bm{r}_i$ into $\bm{R}=[\bm{r}_1, \bm{r}_2, \ldots, \bm{r}_n]$, we obtain
	$$
	\bm{A} = [\bm{a}_1, \bm{a}_2, \ldots, \bm{a}_n] = \bm{C} \bm{U}^{-1} \bm{R},
	$$
	from which the result follows.
	
	In short, we first find $r$ independent columns of $\bm{A}$ into $\bm{C}\in \mathbb{R}^{m\times r}$. From $\bm{C}$, we find a $r\times r$ nonsingular submatrix $\bm{U}$. The $r$ rows of $\bm{A}$ corresponding to entries of $\bm{U}$ can help to reconstruct the columns of $\bm{A}$. Again, the situation is shown in Figure~\ref{fig:skeleton}.
\end{proof}


In case $\bm{A}$ is square and invertible, we have skeleton decomposition $\bm{A}=\bm{C}\bm{U}^{-1} \bm{R}$ where $\bm{C}=\bm{R}=\bm{U}=\bm{A}$ such that the decomposition reduces to $\bm{A} = \bm{A}\bA^{-1}\bm{A}$.


\paragraph{CR decomposition vs skeleton decomposition} We note that CR decomposition and skeleton decomposition shares similar form. Even for the symbols used $\bm{A}=\bm{C}\bm{R}$ for CR decomposition and $\bm{A}=\bm{C}\bm{U}^{-1}\bm{R}$ for skeleton decomposition. 

Both in CR decomposition and skeleton decomposition, we \textbf{can} select the first $r$ independent columns to obtain the matrix $\bm{C}$ (the notation both in CR decomposition and in skeleton decomposition). So $\bm{C}$ in CR decomposition and skeleton decomposition is exactly the same. On the contrary, $\bm{R}$ in CR decomposition is the row reduced echelon form without the zero rows, and $\bm{R}$ in skeleton decomposition is exactly some rows from $\bm{A}$ so that $\bm{R}$ has different meaning in the two decomposition methods. 



\paragraph{A word on the uniqueness of CR decomposition and skeleton decomposition} As mentioned above, both in CR decomposition and skeleton decomposition, we select the first $r$ independent columns to obtain the matrix $\bm{C}$. In this sense, CR decomposition and skeleton decomposition has unique form. 
However, if we select the last $r$ independent columns, we will get a different CR decomposition or skeleton decomposition. We will not discuss this situation here as it is not the main interest of this text.  

To repeat, in the above proof for the existence of the skeleton decomposition, we first find the $r$ independent columns of $\bm{A}$ into the $\bm{C}$ matrix. From $\bm{C}$, we find an $r\times r$ nonsingular submatrix $\bm{U}$. From the submatrix $\bm{U}$, we finally find the final row submatrix $\bm{R}\in \mathbb{R}^{r\times n}$. A further question can be posed that if matrix $\bm{A}$ has rank $r$ and matrix $\bm{C}$ contains $r$ independent columns 
and matrix $\bm{R}$ contains $r$ independent rows, then whether the $r\times r$ ``intersection" of $\bm{C}$ and $\bm{R}$ is invertible or not \footnote{We thank Gilbert Strang for raising this interesting question.}.

\begin{mdframed}[hidealllines=true,backgroundcolor=color1]
	\begin{corollary}\label{corollary:invertible-intersection}
		If matrix $\bm{A} \in \mathbb{R}^{m\times n}$ has rank $r$ and matrix $\bm{C}$ contains $r$ independent columns 
		and matrix $\bm{R}$ contains $r$ independent rows, then the $r\times r$ ``intersection" matrix $\bm{U}$ of $\bm{C}$ and $\bm{R}$ is invertible.
	\end{corollary}
\end{mdframed}
\begin{proof}[of Corollary~\ref{corollary:invertible-intersection}]
	If $I,J$ are the indices of rows and columns selected from $\bm{A}$ into $\bm{R}$ and $\bm{C}$ respectively, then, $\bm{R}$ can be denoted as $\bm{R}=\bm{A}[I, :]$, $\bm{C}$ can be represented as $\bm{C} = \bm{A}[:,J]$, and $\bm{U}$ can be denoted as $\bm{U}=\bm{A}[I,J]$.
	
	Since $\bm{C}$ contains $r$ independent columns of $\bm{A}$, any column $\bm{a}_i$ of $\bm{A}$ can be represented as $\bm{a}_i = \bm{C}\bm{x}_i = \bm{A}[:,J]\bm{x}_i$ for all $i \in \{1,2,\ldots, n\}$. This implies the $r$ entries of $\bm{a}_i$ corresponding to the $I$ indices can be represented by the columns of $\bm{U}$ such that $\bm{a}_i[I] = \bm{U}\bm{x}_i \in \mathbb{R}^{r\times 1}$ for all $i \in \{1,2,\ldots, n\}$, i.e.,
	$$
	\bm{a}_i = \bm{C}\bm{x}_i = \bm{A}[:,J]\bm{x}_i \in \mathbb{R}^{m} \qquad \longrightarrow  \qquad
	\bm{a}_i[I] =\bm{A}[I,J]\bm{x}_i= \bm{U}\bm{x}_i \in \mathbb{R}^{r}.
	$$ 
	Since $\bm{R}$ contains $r$ independent rows of $\bm{A}$, the row rank and column rank of $\bm{R}$ are equal to $r$. Combining the facts above, the $r$ columns of $\bm{R}$ corresponding to indices $J$ (i.e., the $r$ columns of $\bm{U}$) are linearly independent. 
	
	Again, by applying Theorem~\ref{lemma:equal-dimension-rank}, the dimension of the row space of $\bm{U}$ is also equal to $r$ which means there are the $r$ independent rows from $\bm{U}$, and $\bm{U}$ is invertible. 
\end{proof}




\section{Acknowledgments}
We thank Gilbert Strang for raising the question formulated in the Corollary~\ref{corollary:invertible-intersection}, for a stream of ideas and references about the three factorizations from the steps of elimination, and the generous sharing of the manuscript of \citep{strang2021three}.  





















\vskip 0.2in
