{%hackmd 5xqeIJ7VRCGBfLtfMi0_IQ %}

# How to find a basis of the column space?

## Problem

Let

$$
A = \begin{bmatrix}
1 & -5 & -4 & -4 & 5 & 8 \\
-2 & 10 & 8 & 8 & -9 & -14 \\
-5 & 25 & 20 & 20 & -23 & -36 \\
-5 & 25 & 20 & 20 & -23 & -36
\end{bmatrix}\text{ and }
R = \begin{bmatrix}
1 & -5 & -4 & -4 & 0 & -2 \\
0 & 0 & 0 & 0 & 1 & 2 \\
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0
\end{bmatrix}.
$$

It is known that $R$ is the reduced echelon form of $A$. Find a basis for the row space $\Row(A)$.

## Thought

Recall that the reason that we do the row operations is that they do not change the solutions; that is, $\ker(A) = \ker(R)$. For example,

$$
\bh = \begin{bmatrix} 5 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}
$$

satisfies both $A\bh = \bzero$ and $R\bh = \bzero$.

On the other hand, the kernel of a matrix describe the relations of its columns. Let $\ba_1, \ldots, \ba_6$ be the columns of $A$ and $\bb_1, \ldots, \bb_6$ the columns of $R$. The fact $\bh$ is a vector in $\ker(A) = \ker(R)$ indicates that $5\ba_1 + \ba_2 = \bzero$ and $5\bb_1 + \bb_2 = \bzero$.

By observing the matrix $R$, we know $\bb_2, \bb_3, \bb_4, \bb_6$ are in $\vspan(\{\bb_1, \bb_5\})$, and $\{\bb_1, \bb_5\})$ is linearly independent. From our discussion above, this implies $\ba_2, \ba_3, \ba_4, \ba_6$ are in $\vspan(\{\ba_1, \ba_5\})$, and $\{\ba_1, \ba_5\})$ is linearly independent.

Therefore, $\Col(A) = \vspan(\{\ba_1, \ldots, \ba_6\}) = \vspan(\{\ba_1, \ba_5\})$ and $\{\ba_1, \ba_5\}$ is linearly independent. This means $S = \{\ba_1, \ba_5\}$ is a basis of $\Col(A)$.

## Sample answer

By observing the reduced echelon form, we know the indices $1$ and $5$ correspond to the leading variables. Let $\ba_1$ and $\ba_5$ be the columns of $A$ corresponding to the leading variables. Let

$$
\begin{aligned}
S &= \{\ba_1, \ba_5\} \\
&= \left\{
\begin{bmatrix} 1 \\ -2 \\ -5 \\ -5 \end{bmatrix},
\begin{bmatrix} 5 \\ -9 \\ -23 \\ -23 \end{bmatrix}
\right\}.
\end{aligned}
$$

Note that the columns of $A$ and the columns of $R$ have the same linearly dependency. Since the columns of $R$ corresponding to the leading variables span $\Col(R)$, we also have $\vspan(S) = \Col(A)$. Similarly, since the columns of $R$ corresponding to the leading variables form a linearly independent set, we also have that $S$ is linearly independent.

Combining all above results, we know $S$ is a basis of $\Col(A)$.

## Note

Following the arguments above, the set of columns of $A$ corresponding to the leading variables is always a basis of $\Col(A)$.

This means the dimension of $\Col(A)$ is the number of leading variables. This number is called the _rank_ of $A$, denoted as $\rank(A)$.

Run the SageMath code below or simply click [here](https://sagecell.sagemath.org/?q=ewiqir). The code generates some random matrices. Use the code to do some practices by yourself, and then check your answer by modifying `print_ans` in the code.

load("https://raw.githubusercontent.com/jephianlin/LA-notebook/main/lingeo.py")

set_random_seed(None) # replace None with your favorite number
m,n,r = 4,6,2 # m x n matrix with rank r
A, R, pivots = random_good_matrix(m,n,r, return_answer=True)
pretty_print(LatexExpr("A="), A, LatexExpr("\\rightsquigarrow R="), R)

Kb = kernel_matrix(A)
Cb = column_space_matrix(A)
Rb = row_space_matrix(A)

print_ans = "No" # replace No with K, C, R, or All
if print_ans in ["K", "All"]:
    K_basis = [(Kb[:,i//2] if i % 2 == 0 else ",") for i in range(2*(n-r)-1)]
    pretty_print("a basis of ker(A) can be", LatexExpr("\\ \\Big\\{"), *K_basis, LatexExpr("\\Big\\}"))
if print_ans in ["C", "All"]:
    K_basis = [(Cb[:,i//2] if i % 2 == 0 else ",") for i in range(2*r-1)]
    pretty_print("a basis of Col(A) can be", LatexExpr("\\ \\Big\\{"), *K_basis, LatexExpr("\\Big\\}"))
if print_ans in ["R", "All"]:
    K_basis = [(Rb[i//2,:] if i % 2 == 0 else ",") for i in range(2*r-1)]
    pretty_print("a basis of Row(A) can be", LatexExpr("\\ \\Big\\{"), *K_basis, LatexExpr("\\Big\\}"))

*This note can be found at Course website > Learning resources.*