Defining column echelon form as the transpose of reduced row echelon form, how could one go about find a square matrix given its row reduced echelon form (RREF) and column reduced echelon form (CREF)? How do we know when no square matrix can have RRE form and R form that is given?
For example can a matrix have RREF $M_1$, CREF $M_2$,
$$M_1=
\begin{pmatrix}
1&0&-1\\
0&1&3\\
0&0&0
\end{pmatrix}
\;M_2=
\begin{pmatrix}
1&0&0\\
2&0&0\\
0&1&0
\end{pmatrix}$$
The rowrank and columnrank respectively are equal but what method can deduce the form or lack of existence?
Best Answer
For the example you gave, this tells us that $$ M = \left(\begin{array}{ccc} 1 & 0 & -1\\ 2 & 0 & -2\\ 0 & 1 & 3 \end{array}\right) $$ has the desired RREF and CREF.
Proof: To prove that the RREF of $M$ is equal to $M_1$, it suffices to show that $\ker(M) = \ker(M_1)$ (where $\ker(M)$ denotes the kernel AKA nullspace of $M$). It automatically holds that $\ker(M_1) \subseteq \ker(M_2M_1)$, so it suffices to show the reverse inclusion.
Partition off any zero rows of $M_1$ and the zero columns of $M_2$. That is, write $$ M_1 = \pmatrix{R_1\\0}, \quad M_2 = \pmatrix{R_2 & 0}, $$ where $R_1$ has no zero rows and $R_2$ has no zero columns. Note the the rows of $R_1$ are linearly independent and the columns of $R_2$ are linearly independent.
With block-matrix multiplication, note that $$ M_2M_1 = \pmatrix{R_2 & 0} \pmatrix{R_1\\0} = R_2R_1. $$ Because the columns of $R_2$ are linearly independent, we note that $R_2 x = 0 \implies x = 0$. Thus, we have $$ M_2M_1 x = 0 \implies R_2(R_1 x) = 0 \implies R_1 x = 0 \implies M_1 x = 0, $$ so we indeed have $\ker(M_2M_1) \subseteq \ker(M_1)$, which was what we wanted.
Similarly, to prove that the CREF of $M$ is equal to $M_2$, it suffices to show that $\ker(M^T) = \ker(M_2^T)$. However, we have $$ M^T = (M_2M_1)^T = M_1^T M_2^T. $$ Because $M_1^T$ is in CREF and $M_2^T$ is in RREF, the desired result from our previous work.
Note that in general, it is possible for many matrices to have the same RREF and the same CREF. For example: any matrix of the form $$ \pmatrix{a_{11} & a_{12} & 0\\ a_{21} & a_{22} & 0\\0 & 0 & 0} $$ with $a_{11}a_{22} \neq a_{12}a_{21}$ will have RREF and CREF equal to $$ \pmatrix{1&0&0\\0&1&0\\0&0&0}. $$ If we define $R_1$ and $R_2$ as above and let $r$ denote the rank of $M$, then for any $r \times r$ invertible matrix $S$, the matrix $$ R_2 S R_1 $$ will have RREF $M_1$ and CREF $M_2$. In fact, every matrix with this RREF and CREF can be expressed in the above form for some choice of $S$. This can be shown, for instance, with the help of the singular value decomposition.