|
Size: 2467
Comment: Simplifying matrix page names
|
Size: 3146
Comment: Link
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 13: | Line 13: |
| In linear algebra, the '''null space''' is the subspace that satisfies '''''A'''x = 0''. It is notated as ''N('''A''')''. | In linear algebra, the '''null space''' is the subspace that satisfies '''''A'''x = 0''. It is notated as ''N('''A''')''. [[LinearAlgebra/Elimination|Elimination]] does not change the null space of a matrix. |
| Line 15: | Line 15: |
| Algebraically, null spaces have an identity property. Given any valid solution to '''''A'''x = b'', ''any'' combination of null spaces can be added to that solution to create another valid solution, because ''b + 0 = b''. | Null spaces are spanned by null space vectors. There is always a '''zero vector''' in the null space. If a matrix is [[LinearAlgebra/Invertibility|invertible]] however, the zero vector is the ''only'' null space vector. Identifying the set of null space vectors that are not the zero vector gives a [[LinearAlgebra/Basis|basis]] for the null space. The number of dimensions spanned by the null space vectors is called '''nullity''', and it has a direct relation to [[LinearAlgebra/Rank|rank]]. For any matrix '''''A''''' of size ''m x n'' (i.e., there are ''n'' columns), ''rank('''A''') + nullity('''A''') = n''. Null space vectors have an identity property. Given any valid solution to '''''A'''x = b'', ''any'' combination of null spaces can be added to that solution to create another valid solution, because ''b + 0 = b''. |
| Line 21: | Line 25: |
| == Zero Vector as a Solution == | == Solutions == |
| Line 23: | Line 27: |
| All systems of linear equations have a null space containing the '''zero vector'''. For invertible matrices, the zero vector is the ''only'' null space solution. ---- == Solution == Leaving aside the invertible case, the remaining vectors of the null space can be solved for. === Introduction === |
Leaving aside the invertible case, the non-zero vectors of the null space can be solved for. |
| Line 47: | Line 37: |
| This system is rewritten as a linear system and eliminated into: | This system is formulated as a matrix and eliminated into: |
| Line 60: | Line 50: |
| === Identify Free Columns === | === Back-Substitution Procedure === |
| Line 62: | Line 52: |
| For a matrix with ''n'' free columns, the null space has ''n'' dimensions and has ''n'' solutions. | The number of vectors in the null space match the number of free variables. In this case, there are 2. |
| Line 64: | Line 54: |
| Identify the columns with a pivot in the eliminated form. The remaining columns represent '''free variables'''. | The null space vectors can be 'prepopulated' or 'templated' by allowing pivot variables to vary and alternating which free variable is set to 0 or 1. In this case, they are: * ''[w 1 y 0]'' * ''[w 0 y 1]'' |
| Line 66: | Line 58: |
=== Substitute === Because 2 solutions are expected in this example's null space, the solution vectors are pre-populated as: {{{ [w 1 y 0] [w 0 y 1] }}} The ''n''th vector has a 1 in the ''n''th free variable, and a 0 in all other free variables. The pivot variables are left to vary. Solve '''''A'''x = 0'' using these values. For example, the solution using the 1st vector: |
Solve '''''A'''x = 0'' using these values. For example, substituting in the first vector's values gives... |
| Line 104: | Line 81: |
| Leads to the solution ''[-2 1 0 0]''. | ...a null space vector in ''[-2 1 0 0]''. |
| Line 106: | Line 83: |
| Repeat for each vector. The second solution is ''[2 0 -1 1]''. | === Linear Combinations Procedure === Consider combinations of the rows that sum to a zero vector. The first null space vector found was ''[-2 1 0 0]'', corresponding to -2 times the first column and 1 times the second column (and zero times the other two). It should be immediately clear that ''-2*[1 0 0] + 1*[2 0 0] = [0 0 0]''. Following this framework, the second null space vector is ''[2 0 -2 1]'' because ''2*[1 0 0] + -2*[2 2 0] + 1*[2 4 0] = [0 0 0]'' |
Null Space
A null space is a particular category of subspaces. The null space of a system of equations is the set of solutions for which the dependent variables cancel out.
Definition
In linear algebra, the null space is the subspace that satisfies Ax = 0. It is notated as N(A). Elimination does not change the null space of a matrix.
Null spaces are spanned by null space vectors. There is always a zero vector in the null space. If a matrix is invertible however, the zero vector is the only null space vector. Identifying the set of null space vectors that are not the zero vector gives a basis for the null space.
The number of dimensions spanned by the null space vectors is called nullity, and it has a direct relation to rank. For any matrix A of size m x n (i.e., there are n columns), rank(A) + nullity(A) = n.
Null space vectors have an identity property. Given any valid solution to Ax = b, any combination of null spaces can be added to that solution to create another valid solution, because b + 0 = b.
Solutions
Leaving aside the invertible case, the non-zero vectors of the null space can be solved for.
Consider the below system of equations.
w + 2x + 2y + 2z = 1 2w + 4x + 6y + 8z = 5 3w + 6x + 8y + 10z = 6
This system is formulated as a matrix and eliminated into:
┌ ┐ ┌ ┐ ┌ ┐
│[1] 2 2 2│ │ w│ │ 1│
│ 0 0 [2] 4│ │ x│ = │ 3│
│ 0 0 0 0│ │ y│ │ 0│
└ ┘ │ z│ └ ┘
└ ┘
Back-Substitution Procedure
The number of vectors in the null space match the number of free variables. In this case, there are 2.
The null space vectors can be 'prepopulated' or 'templated' by allowing pivot variables to vary and alternating which free variable is set to 0 or 1. In this case, they are:
[w 1 y 0]
[w 0 y 1]
Solve Ax = 0 using these values. For example, substituting in the first vector's values gives...
w + 2x + 2y + 2z = 0 w + 2(1) + 2y + 2(0) = 0 w + 2 + 2y = 0 w = -2 - 2y 2w + 4x + 6y + 8z = 0 2w + 4(1) + 6y + 8(0) = 0 2w + 4 + 6y = 0 2w + 4 + 6y = 0 2(-2 - 2y) + 4 + 6y = 0 -4 - 4y + 4 + 6y = 0 2y = 0 y = 0 w = -2 - 2y w = -2 - 2(0) w = -2
...a null space vector in [-2 1 0 0].
Linear Combinations Procedure
Consider combinations of the rows that sum to a zero vector. The first null space vector found was [-2 1 0 0], corresponding to -2 times the first column and 1 times the second column (and zero times the other two). It should be immediately clear that -2*[1 0 0] + 1*[2 0 0] = [0 0 0].
Following this framework, the second null space vector is [2 0 -2 1] because 2*[1 0 0] + -2*[2 2 0] + 1*[2 4 0] = [0 0 0]