\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


\section{Introduction}
Owing to advantages of high stability, simple instrumentation, label free, and capability of real-time monitoring, the quartz crystal resonator has been applied in a variety of areas, such as, frequency source of communication systems\cite{Y.Watanabe}, gas sensors\cite{P.Si, M.Vagra, L.Zhou, K.W.Liu}, biosensors\cite{H.J.Lim, D.Milioni, D.Chen, K.Noi2, N.Asai}, and so on. Based on the mass loading effect, quartz crystal microbalance (QCM) coated with water-absorbing materials, including graphene oxides\cite{S.Lee}, nanodiamond film \cite{Y.Yao}, TiO$_{2}$ \cite{D.Zhang-1}, SnO$_{2}$ nanowires \cite{N.Gao}, and polydopamine/graphene oxide \cite{D.Zhang-2} have been developed as sensitive humidity sensors. In addition, metal oxide nanofibrous membrane \cite{N.Horzum}, monolayer graphene film \cite{V.V.Quang}, manganese oxide nanosheets \cite{Y.Tokura}, and carbon nanotubes \cite{E.S.Manoso} have also been deposited on QCM to fabricate sensors for detecting volatile organic compounds. Among various biosensors, the electrochemical and surface plasma resonance (SPR) biosensors enable real-time and label-free detection with high sensitivity \cite{K.Tsugimura, S.Kasturi, T.Springer, M.Piliarik, J.Homola}. The QCM biosensor can also monitor binding reaction between ligand and target molecules, providing useful information, such as the concentration of the target and the binding affinity between two molecules. Suthar et al. described a sensitive and selective detection of specific exosomes in human serum using QCM without the need of a secondary label \cite{J.Suthar}. Combining QCM with aptamer-functionalized gold nanoparticles, Chen et al. achieved a detection limit of 0.1 nM for human $\alpha$-thrombin \cite{Q.Chen}. Guha et al. succeed in detecting specific biomarker of bacterial infection with concentration of 1 $\mu$M using a QCM coated with nanomolecular imprinted polymer \cite{A.Guha}. Furthermore, the viscoelastic property or structural change of the attached protein can be evaluated by QCM \cite{T.Shagawa}. Ogi et al. and Hamada et al. monitored the deposition reaction and fibrillation procedure of amyloid $\beta$ peptides using the QCM and internal-reflection-fluorescence microscopy (QCM-TIRFM) system \cite{H.Ogi-SR, H.Hamada}. Shoaib et al. introduced a quartz crystal microbalance with dissipation (QCM-D) sensing strategy to assess the changes in the viscoelastic properties of a cell monolayer in response to oxidative stress \cite{S.Shoaib}. Muramatsu et al. investigated the attachment process and morphological changes of cells through the frequency change of QCM \cite{H.Muramatsu}. However, in a conventional QCM, metal thin films are deposited on both sides of the quartz resonator as electrodes. In addition, mechanical contacts are necessary between the electrodes and the electric connectors. This configuration imposes restriction on the available frequency and deteriorates the quality factor of QCM.

To improve the performance of the QCM biosensor, the wireless and electrodeless QCM has been developed\cite{H.Ogi-AnalChem1, H.Ogi-Proc.Jpn.Acad}. It operates in a wireless manner, allowing the use of extremely thin and high frequency resonator. Because of the higher mass sensitivity of thinner quartz resonator, the  QCM sensitivity can be greatly improved using high frequency and wireless quartz resonator. Noi et al. performed the mass-amplified sandwich assay with bio-nanocapsules (BNCs) using the wireless multichannel QCM biosensor and achieved a detection limit of 10 pg/mL for the detection of C-reactive protein \cite{K.Noi}. However, the thin quartz resonator need to be manually set in the sensor cell, and such subtle and time-consuming procedure deteriorates the practicability.

In our previous study, we demonstrated the QCM biosensor with a naked embedded wireless quartz resonator fabricated using Micro-Electro-Mechanical Systems (MEMS) technology\cite{F.Kato-BB}.  A long fluid microchannel was adopted there in order to obtain steady solution flow and stable baseline, resulting in a large sensor size (20 mm in length). In this study, we present a new MEMS QCM biosensor packaged with a wireless quartz resonator. The length of fluid microchannel has been reduced by half, accordingly, the fabricated MEMS QCM biosensor becomes more compact. Importantly, the compact QCM sensor chip is suitable for mass production and beneficial to device miniaturization. Moreover, the shorter microfluidic channel makes it possible to perform the bioassay with minimal consumption of analyte, which is important especially in diagnostic application. For demonstrating the high sensitivity and usefulness of the MEMS QCM biosensor, we performed the immunoglobulin G (IgG) detection measurement with different concentrations. We then evaluated the affinity between protein A and IgG by studying the frequency response during the binding reaction.

\section{Experiments}
\subsection{Fabrication of MEMS QCM biosensor}

Figure 1(a) illustrates the structure of MEMS QCM biosensor. It consists of glass substrates, the AT-cut quartz resonator, and silicon substrate. Microchannels were constructed on the upper glass substrate and the silicon layer using the MEMS technology similar to the process we previously developed\cite{F. Kato-BB, F.Kato-JJAP}. Here, we briefly explain the procedure: For fabricating the upper glass substrate, the resist mask was patterned on one side of the glass wafer. The isotropic etching was then performed to construct the microchannel and micropillars in the glass wafer. Subsequently, the mask for the inlet and outlet ports were patterned by photolithography on the dry film photoresist mask followed by the sandblast process. Similarly, the microchannel and micropillars were fabricated on the silicon layer using the inductively coupled plasma-reactive ion etching (ICP-RIE) method. The microchannel is 30 $\mu$m in depth, containing a 1.85 $\times$ 1.65 mm$^{2}$ area for embedding the resonator as shown in Fig. 1(b). Micropillars and semi-cylindrical sidewall were built to support and confine the resonator inside the microchannel. The  resonator has an in-plane area of 1.8$\times$1.6 mm$^{2}$. The thickness is 13.5 $\mu$m, corresponding to the fundamental thickness-shear resonant frequency of 125 MHz. To fabricate the quartz resonator, an AT-cut quartz wafer which was bonded to a silicon wafer was first polished to certain thickness, and it was cut into chips with smaller dimensions. The silicon substrate was finally removed by a wet process. Thin films of 2 nm chromium and 8 nm gold were deposited on both sides of the resonator using the radio frequency (RF) magnetron-sputtering method. After inserting the QCM, we packaged the sensor chip using the anodic bonding method. Figure 1(c) illustrates the fabricated MEMS QCM biosensor. The dimension of the sensor chip is 10$\times$5$\times$0.6 mm$^3$. The Q value of the QCM exceeds 80000 in air, but it is about 300 in solution, which is similar with our previously reported value\cite{H.Ogi-AnalChem2}. Figure 2 demonstrates the mass production procedure of many identical MEMS QCM biosensors. Because of the miniaturization we are able to fabricate about 200 identical sensor chips simultaneously using the three pieces of 4 inch wafers.
\begin{figure}
\begin{center}
\includegraphics[width=85mm]{Fig1Structure.eps}
\end{center}
\caption{(a) Components of the MEMS QCM biosensor. (b) Structure of the microchannel. (c) Fabricated MEMS QCM biosensor.}
\label{Fig1Structure}
\end{figure}

\begin{figure*}[t]
\begin{center}
\includegraphics[width=110mm]{Fig2MassProduction.eps}
\end{center}
\caption{Mass production process of the MEMS QCM biosensor. }
\label{Fig2MassProduction}
\end{figure*}

\subsection{Functionalization of QCM surface for IgG detection}
Figure 3 describes the process of QCM surface functionalization and the IgG detection\cite{USE-Zhou}. The QCM was first cleaned with a piranha solution (98\% H$_{2}$SO$_{4}$: 30\% H$_{2}$O$_{2}$ = 7:3) and then rinsed with ultrapure water. To make the self-assembled monolayer (SAM), we injected 10 mM SAM molecules (10-carboxy-decanthiol) in absolute ethanol and incubated overnight at 4 $^{\circ}$C. After rinsing with absolute ethanol and ultrapure water,  a mixture of 100 mM N-hydroxysulfosuccinimide sodium salt (NHS) and 100 mM 1-Ethyl-3-(3-dimethylaminopropyl) carbodiimide hydrochloride (EDC) in ultrapure water was injected, followed by incubation at room temperature for 1 h to activate the SAM terminals. After rinsing with ultrapure water, a 200 $\mu$g/mL protein A in phosphate buffer solution (PBS) was injected. The sensor chip was then incubated for 2 h at room temperature and rinsed by the PBS buffer. At last, a 5 mg/mL bovine serum albumin (BSA) in PBS was injected to block the remaining activated terminals. In the IgG detection measurement, we prepared rabbit IgG (rIgG) in ultrapure water with various concentrations (1--1000 ng/mL). The detection was repeated after dissociating the IgG molecules from QCM surface by flowing glycine-HCl buffer (GHB) solution.

\begin{figure*}[t]
\begin{center}
\includegraphics[width=120mm]{Fig3Functionalization.eps}
\end{center}
\caption{Schematic of the QCM surface functionalization and IgG detection.}
\label{Fig3Functionalization}
\end{figure*}

\begin{figure}[b]
\begin{center}
\includegraphics[width=85mm]{Fig4SensorCell.eps}
\end{center}
\caption{Schematic of the sensor cell.}
\label{Fig4SensorCell}
\end{figure}

\subsection{Materials and reagents}
10-carboxy-decanthiol (\#C385) and EDC (\#W001) were purchased from DOJINDO. NHS (\#087-09371), rIgG (\#148-09551), GHB (0.1M, pH2.2) and PBS (0.1M, pH6.8) were purchased from Wako. Protein A (\#101100) was purchased from Invitrogen. BSA (\#A3059) was purchased from Sigma Aldrich.
\subsection{Experiment system}
In the IgG detection measurement, the sensor chip was set in the homebuilt sensor cell as shown in Fig. 4. The excitation of QCM and signal readout were performed by the line antennas located outside the sensor chip. The line antennas were made of copper on the printed circuit board (PCB); they are 2 mm in width and 35 mm in length. The resonant frequency was monitored by a network analyzer (ZNLE3, Rohde \& Schwarz). A micro-pump was used to flow and circulate the buffer and analyte solutions with a flow rate of 400 $\mu$L/min.

\begin{figure}[b]
\begin{center}
\includegraphics[width=80mm]{Fig5IgGdetection.eps}
\end{center}
\caption{(a) Frequency responses measured by the MEMS QCM biosensor during the IgG-solution flow. (b) Relationship between the amount of the frequency decrease at 35 min from the injection and the IgG concentration.}
\label{Fig5IgGdetection}
\end{figure}

\section{Results and Discussion}
\subsection{IgG detection}
Using the MEMS QCM biosensor, we performed IgG detection with concentration from 1 to 1000 ng/mL. Figure 5(a) shows the frequency responses of the QCM biosensor during the binding reaction between IgG and protein A with different IgG concentrations; after a binding reaction, the IgG molecules were removed by injecting the GHB solution.  After flowing an IgG solution, the resonance frequency starts to decrease as the binding reaction proceeds. Even for the injection of 1 ng/mL IgG, obvious frequency decrease can be observed. The QCM biosensor exhibited lager decreases in frequency  for IgG solutions with higher concentrations, indicating the good reusability of the QCM biosensor. The relationship between the frequency decrease after 35 min from the injection and the IgG concentration is shown in Fig. 5(b), showing a good correlation. Furthermore, we performed the equivalent IgG detection measurement using the surface plasma resonance (SPR) system (Biacore 3000).  The SPR biosensor showed no response to the 1 ng/mL IgG solution and displayed a detection limit of 5 ng/mL, confirming sufficiently higher sensitivity of our newly developed MEMS biosensor.

 In the manual functionalization of QCM surface, the areal density of immobilized SAM molecules and protein A vary with the amount of injected solution and incubation time, resulting in the dispersion of frequency response for higher concentration IgG (1000 ng/mL). Therefore, although without optimization of immobilization condition, the MEMS QCM biosensor shows high sensitivity in IgG detection with a detection limit of 1 ng/mL or lower.

\subsection{Binding affinity evaluation}
We also investigated the binding affinity between IgG and protein A by studying the frequency response of the MEMS QCM biosensor. Assuming the pseudo-first-order reaction between two biomolecules, the frequency of QCM decreases exponentially when the binding reaction proceeds\cite{Y.Liu, H.Ogi-BB},
\begin{equation}
\label{freqLinear}
\frac{\Delta f(t)}{f_{0}}=A\left \{ e^{-(k_{a}C_{IgG}+k_{d})t}-1 \right \}
\end{equation}
with the IgG concentration $C_{IgG}$, the reaction velocity constants for association $k_{a}$ and dissociation $k_{d}$. The equilibrium constant which represents the binding affinity is defined as $K_{A}=k_{a}/k_{d}$. We determined the exponential coefficient $\alpha$ during binding reaction in Fig. 5(a). Fig. 6 shows the relationship between the exponential coefficient and the IgG concentration. The determined values of the kinetics constants are $k_{a}=1.71\times 10^{5}(M^{-1}s^{-1})$, $k_{d}=5.35\times 10^{-4}(s^{-1})$ and $K_{A}=3.20\times 10^{8}(M^{-1})$. The binding affinity between protein A and IgG obtained in this study is in good agreement with reported values in literature (1.59--3.45$\times 10^{8}M^{-1}$(rIgG)\cite{S.C.Kuo}, 1.4$\times 10^{8}M^{-1}$(hIgG)\cite{H.G.Svensson} and 5.54$\times 10^{8}M^{-1}$(hIgG)\cite{K.Noi-JJAP}).

\begin{figure}[t]
\begin{center}
\includegraphics[width=80mm]{Fig6Affinity.eps}
\end{center}
\caption{Relationship between the exponential coefficient of frequency decrease and the IgG concentration.  The dashed line indicates the fitted linear function.}
\label{Fig6Affinity}
\end{figure}

\section{Conclusion}
We presented a MEMS biosensor with a 125-MHz wireless QCM, where a thin quartz resonator was embedded in the microchannel and supported by micropillars. The MEMS QCM biosensor has advantages of compact, low cost, reusable and high sensitivity. Furthermore, a multitude of sensor chips were fabricated simultaneously using the MEMS technology. We functionalized the MEMS QCM biosensor by immobilizing the SAM molecules and protein A on the QCM surface and performed the IgG detection measurements with various concentrations. The MEMS QCM biosensor shows high sensitivity, which succeeded in detecting IgG with concentration as low as 1 ng/mL. We studied the binding affinity between the rIgG and protein A. An affinity of $K_{A}=3.20\times 10^{8}(M^{-1})$ was obtained, which is in good agreement with reported values, indicating the good reliability of the MEMS QCM biosensor. However, because the QCM operates wirelessly by antenna, the signal deteriorates when the QCM is surrounded by solution which contains a large amount of charge carriers. Improvement of signal strength will be our further study.

\section*{Acknowledgement}
This research was supported by Development of Advanced Measurement and Analysis Systems from Japan Science and Technology Agency (Project No. JP-MJSN16B5).