# Deriving left nullspace of matrix from $EA=R$

Let $A$ be an $m\times n$ matrix, $R$ be its row-reduced echelon form, and $E$ be the sequence of matrices $E_k\dots E_1$ used to bring $A$ to $R$, such that $EA = R$. In one of the books on linear algebra it is said that we can use the fact that $EA=R$ to find the basis for the left nullspace of $A$, without the need to bring $A^T$ to the row-reduced echelon form. Is my understanding correct that all we need to do is, since $(EA)^T=A^T$, just row-reduce $R^T$? Or, even better, just read the basis off from $R^T$ without even row-reducing it?

Here are two detailed examples:

Fundamental Theorem of Linear Algebra

Given $\mathbf{A}\in\mathbb{C}^{m\times n}$, the four fundamental subspaces are \begin{align} % \mathbf{C}^{n} = \color{blue}{\mathcal{R} \left( \mathbf{A}^{*} \right)} \oplus \color{red}{\mathcal{N} \left( \mathbf{A} \right)} \\ % \mathbf{C}^{m} = \color{blue}{\mathcal{R} \left( \mathbf{A} \right)} \oplus \color{red} {\mathcal{N} \left( \mathbf{A}^{*} \right)} % \end{align}

Column space

\begin{align} \left[ \begin{array}{c|c} \mathbf{A} & \mathbf{I}_{4} \\ \end{array} \right] & \mapsto \left[ \begin{array}{c|c} \mathbf{E_{A}} & \mathbf{R} \\ \end{array} \right] \\ % \left[ \begin{array}{rrr|cccc} 1 & 1 & -1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ -1 & 0 & 1 & 0 & 0 & 1 & 0 \\ -2 & 1 & 2 & 0 & 0 & 0 & 1 \\ \end{array} \right] & \mapsto \left[ \begin{array}{ccr|rrcc} \boxed{1} & 0 & -1 & 1 & -1 & 0 & 0 \\ 0 & \boxed{1} & 0 & 0 & 1 & 0 & 0 \\\hline 0 & 0 & 0 & \color{red}{1} & \color{red}{-1} & \color{red}{1} & \color{red}{0} \\ 0 & 0 & 0 & \color{red}{2} & \color{red}{-3} & \color{red}{0} & \color{red}{1} \\ \end{array} \right] \tag{1} \end{align}

The boxed pivot entries identify the fundamental columns of the $\color{blue}{range}$ space. The $\color{red}{red}$ row vectors form a span for the $\color{red}{null}$ space.

The column space is now resolved. \begin{align} % \mathbf{C}^{m} = \color{blue}{\mathcal{R} \left( \mathbf{A} \right)} \oplus \color{red} {\mathcal{N} \left( \mathbf{A}^{*} \right)} % % range &= \text{span } \left\{ \, \color{blue}{\left[ \begin{array}{r} 1 \\ 0 \\ -1 \\ -2 \\ \end{array} \right]}, \, \color{blue}{\left[ \begin{array}{r} 1 \\ 1 \\ 0 \\ 1 \\ \end{array} \right]}, \, \right\} % null \oplus \text{span } \left\{ \, \color{red}{ \left[ \begin{array}{r} 1 \\ -1 \\ 1 \\ 0 \\ \end{array} \right], \, \left[ \begin{array}{r} 2 \\ -3 \\ 0 \\ 1 \\ \end{array} \right]} \, \right\}% % \end{align}

Row space

\begin{align} % \left[ \begin{array}{c|c} \mathbf{A}^{T} & \mathbf{I}_{4} \\ \end{array} \right] & \mapsto \left[ \begin{array}{c|c} \mathbf{E_{A^{T}}} & \mathbf{R} \\ \end{array} \right] \\ % \left[ \begin{array}{rcrr|ccc} 1 & 0 & -1 & -2 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ -1 & 0 & 1 & 2 & 0 & 0 & 1 \\ \end{array} \right] &\mapsto \left[ \begin{array}{ccrr|rcc} \boxed{1} & 0 & -1 & -2 & 1 & 0 & 0 \\ 0 & \boxed{1} & 1 & 3 & -1 & 1 & 0 \\\hline 0 & 0 & 0 & 0 & \color{red}{1} & \color{red}{0} & \color{red}{1} \\ \end{array} \right] \tag{2} % \end{align} The row space is now resolved: \begin{align} % \mathbf{C}^{n} = \color{blue}{\mathcal{R} \left( \mathbf{A}^{*} \right)} \oplus \color{red} {\mathcal{N} \left( \mathbf{A} \right)} % % range &= \text{span } \left\{ \, \color{blue}{\left[ \begin{array}{r} 1 \\ 1 \\ -1 \\ \end{array} \right]}, \, \color{blue}{\left[ \begin{array}{r} 0 \\ 1 \\ 0 \\ \end{array} \right]}, \right\} % null \oplus \text{span } \left\{ \, \color{red}{ \left[ \begin{array}{r} 1 \\ 0 \\ 1 \\ \end{array} \right]} \, \right\} % \end{align}

Challenge

As an example for this question, the task is to use the blue row vectors in (1) $$\left[ \begin{array}{ccr|rrcc} \color{blue}{1} & \color{blue}{0} & \color{blue}{-1} & 1 & -1 & 0 & 0 \\ \color{blue}{0} & \color{blue}{1} & \color{blue}{0} & 0 & 1 & 0 & 0 \\\hline 0 & 0 & 0 & \color{red}{1} & \color{red}{-1} & \color{red}{1} & \color{red}{0} \\ 0 & 0 & 0 & \color{red}{2} & \color{red}{-3} & \color{red}{0} & \color{red}{1} \\ \end{array} \right], \tag{3}$$ to find a vector in $$\text{span } \left\{ \, \color{red}{ \left[ \begin{array}{r} 1 \\ 0 \\ 1 \\ \end{array} \right]} \, \right\}. \tag{4}$$

What the reduction in (1) provides is another span $$\color{blue}{\mathcal{R} \left( \mathbf{A}^{*} \right)} = \text{span } \left\{ \, \color{blue}{\left[ \begin{array}{r} 1 \\ 1 \\ -1 \\ \end{array} \right]}, \, \color{blue}{\left[ \begin{array}{r} 0 \\ 1 \\ 0 \\ \end{array} \right]} \, \right\}.$$ And yes, you could look at that span and conclude (4). But this is not "reading" the vectors directly as in the red terms in (1) and (2). For example, can you look at (3) and guess the spans for the column space?

## Conclusion

To summarize: There is no general method to resolve the row space from the reduction matrix $\left[ \begin{array}{c|c} \mathbf{E_{A}} & \mathbf{R} \\ \end{array} \right]$.

The row vectors in the upper left quadrant of $\mathbf{E_{A}}$ are in the span of $\color{blue}{\mathcal{R} \left( \mathbf{A}^{*} \right)}$ and in some simple cases you will be able to deduce a span for $\color{red}{\mathcal{N} \left( \mathbf{A} \right)}$.

$EA = R$

It is trivial to find the vectors the vectors that span the null space of R. for each vector your basis for the left null-space of R

i.e. (0,0,0,0,1) , (0,0,0,1,0) if R has 2 zero rows.

$\mathbf xEA = \mathbf xR = 0$

$\mathbf x E$ is in the null-space of A.

For however many zero rows are in $R$ that many of the bottom rows of $E$ span the left null space of $A.$

It is given that $EA=R$. Since $E$ is product of elementary matrix, it is invertible. So we can write $A=E^{-1}R$. Then take transpose on both sides which gives, $A^T=R^T(E^{-1})^T$. So to find the left nullspace of matrix $A$, we need to solve the system $A^T X=R^T(E^{-1})^TX=0$. Thus we don't need to calculate the row reduced form of $A^T$ to get the left nullspace of $A$.

• But where do you get $E^{-1}$? – sequence May 16 '17 at 14:35
• If A and R are known to us then E is also known and as it is a product of elementary matrix it will be invertible. – Germain May 17 '17 at 3:10
• But that's not the way to easily read of a basis for the left null-space. Finding $E$ (and then $E^{-1}$) takes a lot of overhead, as opposed to finding a basis directly. – sequence May 17 '17 at 3:25
• Maybe I am not understanding, what are you asking here. See, when we have the form R from A, then E is easily found by writing the row or column operations as elementary matrix form and then taking their product. Also finding $E^{-1}$ is not a big task, we need to replace the operations only. Maybe you may follow this link:math.stackexchange.com/questions/677556/… – Germain May 18 '17 at 3:49