Rank–nullity theorem

Rank–nullity theorem "Rank theorem" redirects here. For the rank theorem of multivariable calculus, see constant rank theorem. This article may require cleanup to meet Wikipedia's quality standards. The specific problem is: see talk:Rank–nullity theorem#Terminology. Please help improve this article if you can. (April 2022) (Learn how and when to remove this template message) Rank–nullity theorem The rank–nullity theorem is a theorem in linear algebra, which asserts that the dimension of the domain of a linear map is the sum of its rank (the dimension of its image) and its nullity (the dimension of its kernel).[1][2][3][4] Contents 1 Stating the theorem 1.1 Matrices 2 Proofs 2.1 First proof 2.2 Second proof 3 Reformulations and generalizations 4 Citations 5 References Stating the theorem Let {displaystyle T:Vto W} be a linear transformation between two vector spaces where {displaystyle T} 's domain {displaystyle V} is finite dimensional. Then {displaystyle operatorname {Rank} (T)~+~operatorname {Nullity} (T)~=~dim V,} where {displaystyle operatorname {Rank} (T)~:=~dim(operatorname {Image} (T))qquad {text{ and }}qquad operatorname {Nullity} (T)~:=~dim(operatorname {Ker} (T)).} In other words, {displaystyle dim(operatorname {im} T)+dim(ker T)=dim(operatorname {domain} T).} This theorem can be refined via the splitting lemma to be a statement about an isomorphism of spaces, not just dimensions. Explicitly, since T induces an isomorphism from {displaystyle V/operatorname {Ker} (T)} to {displaystyle operatorname {Image} (T),} the existence of a basis for V that extends any given basis of {displaystyle operatorname {Ker} (T)} implies, via the splitting lemma, that {displaystyle operatorname {Image} (T)oplus operatorname {Ker} (T)cong V.} Taking dimensions, the rank–nullity theorem follows.

Matrices Since {displaystyle operatorname {Mat} _{mtimes n}(mathbb {F} )cong operatorname {Hom} left(mathbb {F} ^{n},mathbb {F} ^{m}right),} [5] matrices immediately come to mind when discussing linear maps. In the case of an {displaystyle mtimes n} matrix, the dimension of the domain is {displaystyle n,} the number of columns in the matrix. Thus the rank–nullity theorem for a given matrix {displaystyle Min operatorname {Mat} _{mtimes n}(mathbb {F} )} immediately becomes {displaystyle operatorname {Rank} (M)+operatorname {Nullity} (M)=n.} Proofs Here we provide two proofs. The first[2] operates in the general case, using linear maps. The second proof[6] looks at the homogeneous system {displaystyle mathbf {Ax} =mathbf {0} } for {displaystyle mathbf {A} in operatorname {Mat} _{mtimes n}(mathbb {F} )} with rank {displaystyle r} and shows explicitly that there exists a set of {displaystyle n-r} linearly independent solutions that span the kernel of {displaystyle mathbf {A} } .

While the theorem requires that the domain of the linear map be finite-dimensional, there is no such assumption on the codomain. This means that there are linear maps not given by matrices for which the theorem applies. Despite this, the first proof is not actually more general than the second: since the image of the linear map is finite-dimensional, we can represent the map from its domain to its image by a matrix, prove the theorem for that matrix, then compose with the inclusion of the image into the full codomain.

First proof Let {displaystyle V,W} be vector spaces over some field {displaystyle mathbb {F} } and {displaystyle T} defined as in the statement of the theorem with {displaystyle dim V=n} .

As {displaystyle operatorname {Ker} Tsubset V} is a subspace, there exists a basis for it. Suppose {displaystyle dim operatorname {Ker} T=k} and let {displaystyle {mathcal {K}}:={v_{1},ldots ,v_{k}}subset operatorname {Ker} (T)} be such a basis.

We may now, by the Steinitz exchange lemma, extend {displaystyle {mathcal {K}}} with {displaystyle n-k} linearly independent vectors {displaystyle w_{1},ldots ,w_{n-k}} to form a full basis of {displaystyle V} .

Let {displaystyle {mathcal {S}}:={w_{1},ldots ,w_{n-k}}subset Vsetminus operatorname {Ker} (T)} such that {displaystyle {mathcal {B}}:={mathcal {K}}cup {mathcal {S}}={v_{1},ldots ,v_{k},w_{1},ldots ,w_{n-k}}subset V} is a basis for {displaystyle V} . From this, we know that {displaystyle operatorname {Im} T=operatorname {Span} T({mathcal {B}})=operatorname {Span} {T(v_{1}),ldots ,T(v_{k}),T(w_{1}),ldots ,T(w_{n-k})}=operatorname {Span} {T(w_{1}),ldots ,T(w_{n-k})}=operatorname {Span} T({mathcal {S}}).} We now claim that {displaystyle T({mathcal {S}})} is a basis for {displaystyle operatorname {Im} T} . The above equality already states that {displaystyle T({mathcal {S}})} is a generating set for {displaystyle operatorname {Im} T} ; it remains to be shown that it is also linearly independent to conclude that it is a basis.

Suppose {displaystyle T({mathcal {S}})} is not linearly independent, and let {displaystyle sum _{j=1}^{n-k}alpha _{j}T(w_{j})=0_{W}} for some {displaystyle alpha _{j}in mathbb {F} } .

Thus, owing to the linearity of {displaystyle T} , it follows that {displaystyle Tleft(sum _{j=1}^{n-k}alpha _{j}w_{j}right)=0_{W}implies left(sum _{j=1}^{n-k}alpha _{j}w_{j}right)in operatorname {Ker} T=operatorname {Span} {mathcal {K}}subset V.} This is a contradiction to {displaystyle {mathcal {B}}} being a basis, unless all {displaystyle alpha _{j}} are equal to zero. This shows that {displaystyle T({mathcal {S}})} is linearly independent, and more specifically that it is a basis for {displaystyle operatorname {Im} T} .

To summarize, we have {displaystyle {mathcal {K}}} , a basis for {displaystyle operatorname {Ker} T} , and {displaystyle T({mathcal {S}})} , a basis for {displaystyle operatorname {Im} T} .

Finally we may state that {displaystyle operatorname {Rank} (T)+operatorname {Nullity} (T)=dim operatorname {Im} T+dim operatorname {Ker} T=|T({mathcal {S}})|+|{mathcal {K}}|=(n-k)+k=n=dim V.} This concludes our proof.

Second proof Let {displaystyle mathbf {A} in operatorname {Mat} _{mtimes n}(mathbb {F} )} with {displaystyle r} linearly independent columns (i.e. {displaystyle operatorname {Rank} (mathbf {A} )=r} ). We will show that: There exists a set of {displaystyle n-r} linearly independent solutions to the homogeneous system {displaystyle mathbf {Ax} =mathbf {0} } . That every other solution is a linear combination of these {displaystyle n-r} solutions.

To do this, we will produce a matrix {displaystyle mathbf {X} in operatorname {Mat} _{ntimes (n-r)}(mathbb {F} )} whose columns form a basis of the null space of {displaystyle mathbf {A} } .

Without loss of generality, assume that the first {displaystyle r} columns of {displaystyle mathbf {A} } are linearly independent. So, we can write {displaystyle mathbf {A} ={begin{pmatrix}mathbf {A} _{1}&mathbf {A} _{2}end{pmatrix}},} where {displaystyle mathbf {A} _{1}in operatorname {Mat} _{mtimes r}(mathbb {F} )} with {displaystyle r} linearly independent column vectors, and {displaystyle mathbf {A} _{2}in operatorname {Mat} _{mtimes (n-r)}(mathbb {F} )} , each of whose {displaystyle n-r} columns are linear combinations of the columns of {displaystyle mathbf {A} _{1}} .

This means that {displaystyle mathbf {A} _{2}=mathbf {A} _{1}mathbf {B} } for some {displaystyle mathbf {B} in operatorname {Mat} _{rtimes (n-r)}} (see rank factorization) and, hence, {displaystyle mathbf {A} ={begin{pmatrix}mathbf {A} _{1}&mathbf {A} _{1}mathbf {B} end{pmatrix}}.} Let {displaystyle mathbf {X} ={begin{pmatrix}-mathbf {B} \mathbf {I} _{n-r}end{pmatrix}},} where {displaystyle mathbf {I} _{n-r}} is the {displaystyle (n-r)times (n-r)} identity matrix. We note that {displaystyle mathbf {X} in operatorname {Mat} _{ntimes (n-r)}(mathbb {F} )} satisfies {displaystyle mathbf {A} mathbf {X} ={begin{pmatrix}mathbf {A} _{1}&mathbf {A} _{1}mathbf {B} end{pmatrix}}{begin{pmatrix}-mathbf {B} \mathbf {I} _{n-r}end{pmatrix}}=-mathbf {A} _{1}mathbf {B} +mathbf {A} _{1}mathbf {B} =mathbf {0} _{mtimes (n-r)}.} Therefore, each of the {displaystyle n-r} columns of {displaystyle mathbf {X} } are particular solutions of {displaystyle mathbf {Ax} =mathbf {0} _{mathbb {F} ^{m}}} .

Furthermore, the {displaystyle n-r} columns of {displaystyle mathbf {X} } are linearly independent because {displaystyle mathbf {Xu} =mathbf {0} _{mathbb {F} ^{n}}} will imply {displaystyle mathbf {u} =mathbf {0} _{mathbb {F} ^{n-r}}} for {displaystyle mathbf {u} in mathbb {F} ^{n-r}} : {displaystyle mathbf {X} mathbf {u} =mathbf {0} _{mathbb {F} ^{n}}implies {begin{pmatrix}-mathbf {B} \mathbf {I} _{n-r}end{pmatrix}}mathbf {u} =mathbf {0} _{mathbb {F} ^{n}}implies {begin{pmatrix}-mathbf {B} mathbf {u} \mathbf {u} end{pmatrix}}={begin{pmatrix}mathbf {0} _{mathbb {F} ^{r}}\mathbf {0} _{mathbb {F} ^{n-r}}end{pmatrix}}implies mathbf {u} =mathbf {0} _{mathbb {F} ^{n-r}}.} Therefore, the column vectors of {displaystyle mathbf {X} } constitute a set of {displaystyle n-r} linearly independent solutions for {displaystyle mathbf {Ax} =mathbf {0} _{mathbb {F} ^{m}}} .

We next prove that any solution of {displaystyle mathbf {Ax} =mathbf {0} _{mathbb {F} ^{m}}} must be a linear combination of the columns of {displaystyle mathbf {X} } .

For this, let {displaystyle mathbf {u} ={begin{pmatrix}mathbf {u} _{1}\mathbf {u} _{2}end{pmatrix}}in mathbb {F} ^{n}} be any vector such that {displaystyle mathbf {Au} =mathbf {0} _{mathbb {F} ^{m}}} . Note that since the columns of {displaystyle mathbf {A} _{1}} are linearly independent, {displaystyle mathbf {A} _{1}mathbf {x} =mathbf {0} _{mathbb {F} ^{m}}} implies {displaystyle mathbf {x} =mathbf {0} _{mathbb {F} ^{r}}} .

Therefore, {displaystyle {begin{array}{rcl}mathbf {A} mathbf {u} &=&mathbf {0} _{mathbb {F} ^{m}}\implies {begin{pmatrix}mathbf {A} _{1}&mathbf {A} _{1}mathbf {B} end{pmatrix}}{begin{pmatrix}mathbf {u} _{1}\mathbf {u} _{2}end{pmatrix}}&=&mathbf {A} _{1}mathbf {u} _{1}+mathbf {A} _{1}mathbf {B} mathbf {u} _{2}&=&mathbf {A} _{1}(mathbf {u} _{1}+mathbf {B} mathbf {u} _{2})&=&mathbf {0} _{mathbb {F} ^{m}}\implies mathbf {u} _{1}+mathbf {B} mathbf {u} _{2}&=&mathbf {0} _{mathbb {F} ^{r}}\implies mathbf {u} _{1}&=&-mathbf {B} mathbf {u} _{2}end{array}}} {displaystyle implies mathbf {u} ={begin{pmatrix}mathbf {u} _{1}\mathbf {u} _{2}end{pmatrix}}={begin{pmatrix}-mathbf {B} \mathbf {I} _{n-r}end{pmatrix}}mathbf {u} _{2}=mathbf {X} mathbf {u} _{2}.} This proves that any vector {displaystyle mathbf {u} } that is a solution of {displaystyle mathbf {Ax} =mathbf {0} } must be a linear combination of the {displaystyle n-r} special solutions given by the columns of {displaystyle mathbf {X} } . And we have already seen that the columns of {displaystyle mathbf {X} } are linearly independent. Hence, the columns of {displaystyle mathbf {X} } constitute a basis for the null space of {displaystyle mathbf {A} } . Therefore, the nullity of {displaystyle mathbf {A} } is {displaystyle n-r} . Since {displaystyle r} equals rank of {displaystyle mathbf {A} } , it follows that {displaystyle operatorname {Rank} (mathbf {A} )+operatorname {Nullity} (mathbf {A} )=n} . This concludes our proof.

Reformulations and generalizations This theorem is a statement of the first isomorphism theorem of algebra for the case of vector spaces; it generalizes to the splitting lemma.

In more modern language, the theorem can also be phrased as saying that each short exact sequence of vector spaces splits. Explicitly, given that {displaystyle 0rightarrow Urightarrow Vmathbin {overset {T}{rightarrow }} Rrightarrow 0} is a short exact sequence of vector spaces, then {displaystyle Uoplus Rcong V} , hence {displaystyle dim(U)+dim(R)=dim(V).} Here R plays the role of im T and U is ker T, i.e. {displaystyle 0rightarrow ker Tmathbin {hookrightarrow } Vmathbin {overset {T}{rightarrow }} operatorname {im} Trightarrow 0} In the finite-dimensional case, this formulation is susceptible to a generalization: if 0 → V1 → V2 → ⋯ → Vr → 0 is an exact sequence of finite-dimensional vector spaces, then[7] {displaystyle sum _{i=1}^{r}(-1)^{i}dim(V_{i})=0.} The rank–nullity theorem for finite-dimensional vector spaces may also be formulated in terms of the index of a linear map. The index of a linear map {displaystyle Tin operatorname {Hom} (V,W)} , where {displaystyle V} and {displaystyle W} are finite-dimensional, is defined by {displaystyle operatorname {index} T=dim operatorname {Ker} (T)-dim operatorname {Coker} T.} Intuitively, {displaystyle dim operatorname {Ker} T} is the number of independent solutions {displaystyle v} of the equation {displaystyle Tv=0} , and {displaystyle dim operatorname {Coker} T} is the number of independent restrictions that have to be put on {displaystyle w} to make {displaystyle Tv=w} solvable. The rank–nullity theorem for finite-dimensional vector spaces is equivalent to the statement {displaystyle operatorname {index} T=dim V-dim W.} We see that we can easily read off the index of the linear map {displaystyle T} from the involved spaces, without any need to analyze {displaystyle T} in detail. This effect also occurs in a much deeper result: the Atiyah–Singer index theorem states that the index of certain differential operators can be read off the geometry of the involved spaces.

Citations ^ Axler (2015) p. 63, §3.22 ^ Jump up to: a b Friedberg, Insel & Spence (2014) p. 70, §2.1, Theorem 2.3 ^ Katznelson & Katznelson (2008) p. 52, §2.5.1 ^ Valenza (1993) p. 71, §4.3 ^ Friedberg, Insel & Spence (2014) pp. 103-104, §2.4, Theorem 2.20 ^ Banerjee, Sudipto; Roy, Anindya (2014), Linear Algebra and Matrix Analysis for Statistics, Texts in Statistical Science (1st ed.), Chapman and Hall/CRC, ISBN 978-1420095388 ^ Zaman, Ragib. "Dimensions of vector spaces in an exact sequence". Mathematics Stack Exchange. Retrieved 27 October 2015. References Axler, Sheldon (2015). Linear Algebra Done Right. Undergraduate Texts in Mathematics (3rd ed.). Springer. ISBN 978-3-319-11079-0. Banerjee, Sudipto; Roy, Anindya (2014), Linear Algebra and Matrix Analysis for Statistics, Texts in Statistical Science (1st ed.), Chapman and Hall/CRC, ISBN 978-1420095388 Friedberg, Stephen H.; Insel, Arnold J.; Spence, Lawrence E. (2014). Linear Algebra (4th ed.). Pearson Education. ISBN 978-0130084514. Meyer, Carl D. (2000), Matrix Analysis and Applied Linear Algebra, SIAM, ISBN 978-0-89871-454-8. Katznelson, Yitzhak; Katznelson, Yonatan R. (2008). A (Terse) Introduction to Linear Algebra. American Mathematical Society. ISBN 978-0-8218-4419-9. Valenza, Robert J. (1993) [1951]. Linear Algebra: An Introduction to Abstract Mathematics. Undergraduate Texts in Mathematics (3rd ed.). Springer. ISBN 3-540-94099-5. Categories: Theorems in linear algebraIsomorphism theorems

Si quieres conocer otros artículos parecidos a Rank–nullity theorem puedes visitar la categoría Isomorphism theorems.

Deja una respuesta

Tu dirección de correo electrónico no será publicada.

Subir

Utilizamos cookies propias y de terceros para mejorar la experiencia de usuario Más información