I Proof of Column Extraction Theorem for Finding a Basis for Col(A)

mattTch
Messages
2
Reaction score
0
TL;DR Summary
Let A be an m×n matrix. I am not sure why it's immediately obvious that the set B containing all and only the column vectors of R = RREF(A) which have leading ones, forms a basis for R. In particular, why is it the case that Span(B) = Col(R)? FYI: The linear independence of B is obvious to me.
Theorem: The columns of A which correspond to leading ones in the reduced row echelon form of A form a basis for Col(A). Moreover, dimCol(A)=rank(A).
 
Physics news on Phys.org
Consider:

1. If \alpha : V \to W is a linear map and B = \{b_i\} is a basis for V, then \alpha(B) spans \alpha(V). This follows from linearity of \alpha: If v \in V then v = \sum_i a_ib_i and <br /> \alpha(v) = \alpha\left(\sum _ia_i b_i\right) = \sum_i a_i \alpha(b_i).

2. The ith column of a matrix is the image of the ith standard basis vector.

3. It follows from the definition of RREF that columns which don't have a leading 1 are linear combinations of the columns which do.
 
Why does 3 follow from the definition of RREF?
 
mattTch said:
Why does 3 follow from the definition of RREF?
Can chip in? If I've understood your question this might help.

Consider an example RREF matrix:

##\begin{bmatrix}
1 & 0 & 2 & 0 & 8\\
0 & 1 & 7 & 0 & 3\\
0 & 0 & 0 & 1 & 2\\
0 & 0 & 0 & 0 & 0
\end{bmatrix} ##

Some columns contain a leading '1' (with zeroes for all other elements). These are the basis columns.

Other columns do not contain a leading '1'. These are non-basis columns.

The basis columns here are ##C_1 = \begin{bmatrix}
1\\
0\\
0\\
0
\end{bmatrix}##, ##C_2 = \begin{bmatrix}
0\\
1\\
0\\
0
\end{bmatrix}## and ##C_4 = \begin{bmatrix}
0\\
0\\
1\\
0
\end{bmatrix}##.

From inspection it should be clear that any non-basis column can be constructed as a linear combination of the basis columns, e.g. ##C_5 = 8C_1 + 3C_2 + 2C_4##.

That’s because every non-zero coefficient in a non-basis column is a simple multiple of the ‘1’ in a basis column.
 
Thread 'Determine whether ##125## is a unit in ##\mathbb{Z_471}##'
This is the question, I understand the concept, in ##\mathbb{Z_n}## an element is a is a unit if and only if gcd( a,n) =1. My understanding of backwards substitution, ... i have using Euclidean algorithm, ##471 = 3⋅121 + 108## ##121 = 1⋅108 + 13## ##108 =8⋅13+4## ##13=3⋅4+1## ##4=4⋅1+0## using back-substitution, ##1=13-3⋅4## ##=(121-1⋅108)-3(108-8⋅13)## ... ##= 121-(471-3⋅121)-3⋅471+9⋅121+24⋅121-24(471-3⋅121## ##=121-471+3⋅121-3⋅471+9⋅121+24⋅121-24⋅471+72⋅121##...
Back
Top