Editing Linear subspace (section)

==Algorithms==
Most algorithms for dealing with subspaces involve [[row reduction]]. This is the process of applying [[elementary row operation]]s to a matrix, until it reaches either [[row echelon form]] or [[reduced row echelon form]]. Row reduction has the following important properties:
# The reduced matrix has the same null space as the original.
# Row reduction does not change the span of the row vectors, i.e. the reduced matrix has the same row space as the original.
# Row reduction does not affect the linear dependence of the column vectors.

===Basis for a row space===
:'''Input''' An ''m''&nbsp;×&nbsp;''n'' matrix ''A''.
:'''Output''' A basis for the row space of ''A''.
:# Use elementary row operations to put ''A'' into row echelon form.
:# The nonzero rows of the echelon form are a basis for the row space of ''A''.
See the article on [[row space]] for an [[Row and column spaces#Basis 2|example]].

If we instead put the matrix ''A'' into reduced row echelon form, then the resulting basis for the row space is uniquely determined. This provides an algorithm for checking whether two row spaces are equal and, by extension, whether two subspaces of ''K''<sup>''n''</sup> are equal.

===Subspace membership===
:'''Input''' A basis {'''b'''<sub>1</sub>, '''b'''<sub>2</sub>, ..., '''b'''<sub>''k''</sub>} for a subspace ''S'' of ''K''<sup>''n''</sup>, and a vector '''v''' with ''n'' components.
:'''Output''' Determines whether '''v''' is an element of ''S''
:# Create a (''k''&nbsp;+&nbsp;1)&nbsp;×&nbsp;''n'' matrix ''A'' whose rows are the vectors '''b'''<sub>1</sub>,&nbsp;...&nbsp;,&nbsp;'''b'''<sub>''k''</sub> and '''v'''.
:# Use elementary row operations to put ''A'' into row echelon form.
:# If the echelon form has a row of zeroes, then the vectors {{nowrap| {'''b'''<sub>1</sub>, ..., '''b'''<sub>''k''</sub>, '''v'''} }} are linearly dependent, and therefore {{nowrap| '''v''' ∈ ''S''}}.

===Basis for a column space===
:'''Input''' An ''m''&nbsp;×&nbsp;''n'' matrix ''A''
:'''Output''' A basis for the column space of ''A''
:# Use elementary row operations to put ''A'' into row echelon form.
:# Determine which columns of the echelon form have [[Row echelon form|pivots]]. The corresponding columns of the original matrix are a basis for the column space.
See the article on column space for an [[Column space#Basis|example]].

This produces a basis for the column space that is a subset of the original column vectors. It works because the columns with pivots are a basis for the column space of the echelon form, and row reduction does not change the linear dependence relationships between the columns.

===Coordinates for a vector===
:'''Input''' A basis {'''b'''<sub>1</sub>, '''b'''<sub>2</sub>, ..., '''b'''<sub>''k''</sub>} for a subspace ''S'' of ''K''<sup>''n''</sup>, and a vector {{nowrap| '''v''' ∈ ''S''}}
:'''Output''' Numbers ''t''<sub>1</sub>, ''t''<sub>2</sub>, ..., ''t''<sub>''k''</sub> such that {{nowrap|1= '''v''' = ''t''<sub>1</sub>'''b'''<sub>1</sub> + ··· + ''t''<sub>''k''</sub>'''b'''<sub>''k''</sub>}}
:# Create an [[augmented matrix]] ''A'' whose columns are '''b'''<sub>1</sub>,...,'''b'''<sub>''k''</sub> , with the last column being '''v'''.
:# Use elementary row operations to put ''A'' into reduced row echelon form.
:# Express the final column of the reduced echelon form as a linear combination of the first ''k'' columns. The coefficients used are the desired numbers {{nowrap| ''t''<sub>1</sub>, ''t''<sub>2</sub>, ..., ''t''<sub>''k''</sub>}}. (These should be precisely the first ''k'' entries in the final column of the reduced echelon form.)
If the final column of the reduced row echelon form contains a pivot, then the input vector '''v''' does not lie in ''S''.

===Basis for a null space===
:'''Input''' An ''m''&nbsp;×&nbsp;''n'' matrix ''A''.
:'''Output''' A basis for the null space of ''A''
:# Use elementary row operations to put ''A'' in reduced row echelon form.
:# Using the reduced row echelon form, determine which of the variables {{nowrap| ''x''<sub>1</sub>, ''x''<sub>2</sub>, ..., ''x<sub>n</sub>''}} are free. Write equations for the dependent variables in terms of the free variables.
:# For each free variable ''x<sub>i</sub>'', choose a vector in the null space for which {{nowrap|1= ''x<sub>i</sub>'' = 1}} and the remaining free variables are zero. The resulting collection of vectors is a basis for the null space of ''A''.
See the article on null space for an [[Kernel (matrix)#Basis|example]].

===Basis for the sum and intersection of two subspaces===
Given two subspaces {{mvar|U}} and {{mvar|W}} of {{mvar|V}}, a basis of the sum <math>U + W</math> and the intersection <math>U \cap W</math> can be calculated using the [[Zassenhaus algorithm]].

===Equations for a subspace===
:'''Input''' A basis {'''b'''<sub>1</sub>, '''b'''<sub>2</sub>, ..., '''b'''<sub>''k''</sub>} for a subspace ''S'' of ''K''<sup>''n''</sup>
:'''Output''' An (''n''&nbsp;−&nbsp;''k'')&nbsp;×&nbsp;''n'' matrix whose null space is ''S''.
:# Create a matrix ''A'' whose rows are {{nowrap| '''b'''<sub>1</sub>, '''b'''<sub>2</sub>, ..., '''b'''<sub>''k''</sub>}}.
:# Use elementary row operations to put ''A'' into reduced row echelon form.
:# Let {{nowrap| '''c'''<sub>1</sub>, '''c'''<sub>2</sub>, ..., '''c'''<sub>''n''</sub> }} be the columns of the reduced row echelon form. For each column without a pivot, write an equation expressing the column as a linear combination of the columns with pivots.
:# This results in a homogeneous system of ''n'' − ''k'' linear equations involving the variables '''c'''<sub>1</sub>,...,'''c'''<sub>''n''</sub>. The {{nowrap| (''n'' − ''k'') × ''n''}} matrix corresponding to this system is the desired matrix with nullspace ''S''.
; Example
:If the reduced row echelon form of ''A'' is

::<math>\left[ \begin{alignat}{6}
1 && 0 && -3 && 0 &&  2 && 0 \\
0 && 1 &&  5 && 0 && -1 && 4 \\
0 && 0 &&  0 && 1 &&  7 && -9 \\
0 && \;\;\;\;\;0 &&  \;\;\;\;\;0 && \;\;\;\;\;0 &&  \;\;\;\;\;0 && \;\;\;\;\;0 \end{alignat} \,\right] </math>

:then the column vectors {{nowrap| '''c'''<sub>1</sub>, ..., '''c'''<sub>6</sub>}} satisfy the equations

::<math> \begin{alignat}{1}
\mathbf{c}_3 &= -3\mathbf{c}_1 + 5\mathbf{c}_2 \\
\mathbf{c}_5 &= 2\mathbf{c}_1 - \mathbf{c}_2 + 7\mathbf{c}_4 \\
\mathbf{c}_6 &= 4\mathbf{c}_2 - 9\mathbf{c}_4
\end{alignat}</math>

:It follows that the row vectors of ''A'' satisfy the equations

::<math> \begin{alignat}{1}
x_3 &= -3x_1 + 5x_2 \\
x_5 &= 2x_1 - x_2 + 7x_4 \\
x_6 &= 4x_2 - 9x_4.
\end{alignat}</math>

:In particular, the row vectors of ''A'' are a basis for the null space of the corresponding matrix.