Given A=LU factorization, prove that the basis of column space A is the columns of L that correspond to the pivot columns of U

Question

I understand that the basis of column space A is just the columns of A that correspond to the pivot columns of U. This is because U is just the reduced row echelon form.

However, as mentioned in the title, I am having difficulty grasping why columns of L that correspond to the pivot columns of U form the basis of column space A?

Just to give u guys a concrete example of what does the proof statement mean:

$$A = LU$$

As you can see that the first 2 columns of U are the pivot columns, $$U = \begin{bmatrix}5&0&3\\0&1&1\\0&0&0\end{bmatrix}$$

Based on the proof statement, the first 2 columns of L form the basis for A $$L = \begin{bmatrix}1&0&0\\2&1&0\\-1&0&1\end{bmatrix}$$

I am supposed to prove why basis b for column space of A is the first 2 columns of L.

$$b = \left\{ \begin{bmatrix}1\\2\\-1\end{bmatrix},\begin{bmatrix}0\\1\\0\end{bmatrix} \right\} $$

In short, how to prove that the basis b for column space of A is the columns of L that correspond to the pivot columns of U?

I appreciate your help!

Answer 1

$A=LU \Rightarrow Col (A)=Col (LU)=Col \big(\begin{bmatrix}1&0&0\\2&1&0\\-1&0&1\end{bmatrix}\begin{bmatrix}5&0&3\\0&1&1\\0&0&0\end{bmatrix}\big)=span (5 [1, 2, -1]^t,[0, 1, 0]^t)$

The idea is that non -pivotal columns of U contribute nothing to Col (LU). In the above example, 3rd column of U is non pivotal (doesn't have any pivots) and hence in Col (LU) expression above, 3rd column is missing.

Let's generalize this for a special case of square matrices (where U is such that pivots appear on diagonals):
Let LU factorization of A exist such that A=LU (assume n by n order). U is in row echelon form and L is a lower triangular matrix with 1's on diagonal. Assume U has k ($\lt n$) pivots $a_{ii} \ne 0$ for $i={1,2,3,...,k}$. Then $Col (A)=Col (LU)=span (Lu_1 ,Lu_2, ...,Lu_{n-1},Lu_n))$ ,
where $u_i$ is the ith column of U. Since L is invertible, $Col (A)=Col(LU)=span(Lu_1,Lu_2,...,Lu_k) \tag{A}$
Remarks:
1) Col () is column space.
2) (A) is true because suppose that for some real $c_i$'s where $i={1,2,3,4,...,k}$ such that $c_1 (Lu_1)+c_2 (Lu_2)+...+c_k(Lu_k)=0$$\Rightarrow L(c_1u_1+c_2u_2+...+c_ku_k)=0$$ \Rightarrow c_1u_1+c_2u_2+...+c_ku_k=0 \Rightarrow c_1=c_2=c_3=...=c_k=0$ [Since $u_i$'s are pivotal columns and hence linearly independent.]

Answer 2

Thanks guys for your input @Ian @Koro. However, I manage to find a concise and elegant answer to this.

B = LU

The main reason is U is an upper triangular in reduced row-echelon form. And this is always a property of LU factorization.

Recall in matrix multiplication: The product of any 2 matrices is the sum of rows and cols. To derive matrix B, it will be the sum of each column L dot product of the corresponding individual row of U. For example, first column of L dot product the first row of U. The second column of L dot product the second row of U, etc. And then finally adding all together.

Since U is an upper triangular matrix in reduced row echelon form, you can guarantee that the first column of the matrix B(matrix multiplication of LU) will just be the first row pivot of U dot product by the first column of L. Note that the second row pivot of U dot product the second column of L will not interfere with the first column of B because U is an upper triangular matrix.

More explicitly, the first entry of the second pivot row of U is 0 due to U being an upper triangular matrix. Hence if I dot product the second column of L and the second pivot row of U, the result matrix will have all zero in the first column which does not interfere with the first column of B. Without loss of generality, this can be applied to the remaining rows.

Since the columns of B are derived from a linear combination of the pivot columns of L, by basis definition, we can then conclude that the pivot columns of L form the basis for col(A).

Answer 3

$L$ is always set up to be invertible. (This is true even if $A$ is rectangular: when $A$ is $m \times n$, $L$ is $m \times m$ and $U$ is $m \times n$, and $L$ is triangular with diagonal elements of $1$.)

Consequently linear independence and spanning are both preserved under the action of $L$. So if $\{ u_k \}$ is a basis for the column space of $U$ then $\{ Lu_k \}$ is a basis for the column space of $A$. It is hopefully clear that the pivot columns of $U$ form a basis for its column space. So $\{ Lu_{j_k} \}$ is a basis for the column space of $A$ if $j_k$ is the sequence of indices of pivots in $U$. Each such $L u_{j_k}$ is a linear combination of columns of $L$ (as is any other matrix-vector product $Lx$).

Now the question is, which columns of $L$ actually show up in the combinations $\{ L u_{j_k} \}$?

The answer is not the columns $\ell_{j_k}$, which seems to be what your statement says. It is simply the first $r$ columns of $L$, where $r$ is the rank of $A$, because $U$ only has nonzero entries in its first $r$ rows since it has $r$ pivots.

Here we have implicitly assumed that $A$ was chosen such that a regular $LU$ decomposition exists. In general only a $PA=LU$ decomposition exists (i.e. row interchanges may be required even in exact arithmetic) and in this case a basis of the column space of $A$ consists of the first $r$ columns of $P^T L$ (again because $U$ only has any nonzero entries in its first $r$ rows).

Now what is true is that a basis of the column space of $A$ consists of the columns of $A$ itself which correspond to pivot columns of $U$.

I think this is most easily seen by applying the theorem: if $A$ and $B$ are row equivalent then they have the same null space. (This follows immediately from knowing that Gaussian elimination works, since performing steps of Gaussian elimination on a matrix augmented by the zero vector doesn't change that vector being the zero vector.) Consequently $\{ b_{j_k} \}$ is a linearly independent set of columns of $B$ if and only if $\{ a_{j_k} \}$ is a linearly independent set of columns of $A$. Thus if we take all the pivot columns of $U$, that set is linearly independent, and if we add any other columns of $U$ to it, then it ceases to be linearly independent. So the same is true of the corresponding columns of $A$, and thus those columns are a basis for the column space of $A$.