3.1 Vector Spaces, Linear Maps and Linear Systems
Vector spaces, subspaces, bases and dimension (with subspace counts over finite fields), linear maps and the rank–nullity theorem, matrices of linear maps and change of basis, and the rank criteria that decide every linear system — the foundation that every GATE MA linear algebra question stands on.
Solve a homogeneous system of three equations in five unknowns and you get a two-parameter family of solutions; differentiate polynomials of degree at most $3$ and you lose exactly one dimension's worth of information (the constants); rotate the plane and nothing is lost at all. These are three faces of one theorem. Linear algebra replaces the pictures by a single language — vector spaces, subspaces, bases, dimension, linear maps — in which "how many parameters", "how much is lost" and "is the map reversible" become the numbers dimension, nullity and rank, tied together by the rank–nullity theorem. Choosing a basis turns every linear map into a matrix, and changing the basis changes the matrix by the similarity rule $P^{-1}AP$; the whole of Section 3.2 (eigenvalues, diagonalisation, Jordan form) is the search for the basis in which that matrix is simplest.
GATE MA tests this material every year, mostly in short computational form: the dimension of a space of matrices or polynomials cut out by conditions, the rank or nullity of a concrete map, the number of subspaces of a vector space over a finite field, the values of a parameter for which a system has no solution, one solution or infinitely many, and MSQs that ask which rank statements are always true. Every one of these is a two-line argument once you know exactly which theorem applies — and which plausible-looking statements are false. This section gives the theorems with their proofs, the computations, and the counterexamples.
Vector Spaces, Subspaces, Bases and Dimension
Throughout, $\mathbb{F}$ denotes the field of scalars: $\mathbb{R}$ or $\mathbb{C}$ in almost every question, and occasionally a finite field $\mathbb{F}_q$ with $q$ elements (for example $\mathbb{F}_2=\{0,1\}$ with $1+1=0$) in counting questions.
A vector space over $\mathbb{F}$ is a set $V$ with an addition $V\times V\to V$ and a scalar multiplication $\mathbb{F}\times V\to V$ such that, for all $u,v,w\in V$ and $a,b\in\mathbb{F}$: $(V,+)$ is an abelian group (addition is associative and commutative, there is a zero vector $0$, and every $v$ has a negative $-v$); and $a(u+v)=au+av$, $(a+b)v=av+bv$, $(ab)v=a(bv)$, $1v=v$.
Standard examples: $\mathbb{F}^n$; the space $M_{m\times n}(\mathbb{F})$ of $m\times n$ matrices (and $M_n(\mathbb{F})=M_{n\times n}(\mathbb{F})$); the space $P_n(\mathbb{F})$ of polynomials of degree at most $n$ (with the zero polynomial); the space $\mathbb{F}[x]$ of all polynomials; the space $C[a,b]$ of continuous real functions on $[a,b]$; the space of all real sequences.
From the axioms, $0v=0$, $a0=0$ and $(-1)v=-v$; for instance $0v=(0+0)v=0v+0v$, and adding $-0v$ gives $0v=0$. The scalars matter: $\mathbb{C}^n$ is a vector space over $\mathbb{C}$ and also, by restricting the scalars, over $\mathbb{R}$, and the two structures have different dimensions.
- A nonempty subset $W\subseteq V$ is a subspace if and only if $u+cv\in W$ for all $u,v\in W$ and $c\in\mathbb{F}$.
- Any intersection of subspaces is a subspace.
- For subspaces $U,W$ of $V$: $U\cup W$ is a subspace if and only if $U\subseteq W$ or $W\subseteq U$.
Proof. (1) If $W$ is a subspace the condition holds. Conversely, take $u=v\in W$ and $c=-1$: $0=u-u\in W$. Then $cv=0+cv\in W$, and $u+v=u+1v\in W$. (2) Each subspace contains $0$ and is closed under $u+cv$, so the intersection is too. (3) If one contains the other, the union is the larger one. Suppose neither contains the other and pick $u\in U\setminus W$ and $w\in W\setminus U$. If $U\cup W$ were a subspace, $u+w$ would lie in $U$ or in $W$. If $u+w\in U$ then $w=(u+w)-u\in U$, a contradiction; if $u+w\in W$ then $u=(u+w)-w\in W$, again a contradiction. ∎
Let $S=\{v_1,\dots,v_k\}\subseteq V$. A linear combination of $S$ is a vector $c_1v_1+\cdots+c_kv_k$; the set of all of them is the span $\operatorname{span}S$, the smallest subspace containing $S$ (by convention $\operatorname{span}\varnothing=\{0\}$). $S$ is linearly independent if $c_1v_1+\cdots+c_kv_k=0$ forces $c_1=\cdots=c_k=0$, and dependent otherwise. An infinite set is independent if each of its finite subsets is.
A basis of $V$ is a linearly independent set that spans $V$. If $V$ has a finite basis, $V$ is finite-dimensional and its dimension $\dim V$ (or $\dim_{\mathbb{F}}V$) is the number of vectors in a basis; $\dim\{0\}=0$. If $\mathcal{B}=(b_1,\dots,b_n)$ is an ordered basis, every $v\in V$ is $v=a_1b_1+\cdots+a_nb_n$ for unique scalars, the coordinates $[v]_{\mathcal{B}}=(a_1,\dots,a_n)^{\mathsf T}$.
Uniqueness of coordinates is just independence: two expressions of $v$ subtract to a vanishing combination of the $b_i$. The definition of dimension makes sense only because all bases have the same size, which is the content of the next theorem.
- Exchange inequality. If $V$ is spanned by $n$ vectors, then every linearly independent subset of $V$ has at most $n$ vectors.
- Consequently any two bases of a finite-dimensional space have the same number of vectors.
- Let $\dim V=n$. Then: any $n$ linearly independent vectors form a basis; any $n$ vectors spanning $V$ form a basis; every linearly independent set can be extended to a basis; every finite spanning set contains a basis.
- If $W$ is a subspace of $V$ with $\dim V=n$, then $W$ is finite-dimensional, $\dim W\le n$, and $\dim W=n$ only if $W=V$.
Proof. (1) Suppose $V=\operatorname{span}\{w_1,\dots,w_n\}$ and $v_1,\dots,v_m\in V$ with $m\gt n$. Write $v_j=\sum_{i=1}^na_{ij}w_i$. For scalars $c_1,\dots,c_m$,
$$\sum_{j=1}^mc_jv_j=\sum_{i=1}^n\Big(\sum_{j=1}^ma_{ij}c_j\Big)w_i .$$So it suffices to find $c\ne0$ with $\sum_ja_{ij}c_j=0$ for $i=1,\dots,n$: a homogeneous linear system of $n$ equations in $m\gt n$ unknowns. Such a system always has a nontrivial solution, by induction on $n$: for $n=1$ it is one equation in at least two unknowns; in general, if all coefficients of $c_1$ vanish, take $c=(1,0,\dots,0)$; otherwise solve one equation for $c_1$ and substitute it into the others, which leaves $n-1$ equations in the $m-1\gt n-1$ unknowns $c_2,\dots,c_m$; a nontrivial solution of those, with the corresponding $c_1$, works. Hence $v_1,\dots,v_m$ are dependent.
(2) If $\mathcal{B}$ and $\mathcal{B}'$ are bases, $\mathcal{B}$ is independent and $\mathcal{B}'$ spans, so $|\mathcal{B}|\le|\mathcal{B}'|$; by symmetry they are equal. (3) If $v_1,\dots,v_n$ are independent but do not span, choose $v\notin\operatorname{span}\{v_1,\dots,v_n\}$; then $v_1,\dots,v_n,v$ are independent (a nontrivial relation would have to involve $v$ and would express it through the others), contradicting (1). The same step, repeated, extends any independent set: while it does not span, add a vector outside its span; by (1) this stops after at most $n$ vectors, with a basis. If $n$ vectors span but are dependent, one of them is a combination of the others and can be removed without changing the span; repeating, we reach an independent spanning set with fewer than $n$ vectors, contradicting (2). The same removal argument extracts a basis from any finite spanning set. (4) An independent subset of $W$ is an independent subset of $V$, so it has at most $n$ vectors; a largest one spans $W$ (otherwise it could be enlarged), so it is a basis of $W$ and $\dim W\le n$. If $\dim W=n$, a basis of $W$ is $n$ independent vectors of $V$, hence a basis of $V$ by (3), and $W=V$. ∎
| space (over $\mathbb{F}$ unless stated) | dimension | a basis |
|---|---|---|
| $\mathbb{F}^n$ | $n$ | $e_1,\dots,e_n$ |
| $M_{m\times n}(\mathbb{F})$ | $mn$ | matrix units $E_{ij}$ |
| $P_n(\mathbb{F})$, degree $\le n$ | $n+1$ | $1,x,\dots,x^n$ |
| diagonal $n\times n$ | $n$ | $E_{ii}$ |
| symmetric / upper triangular $n\times n$ | $\tfrac{n(n+1)}2$ | $E_{ij}+E_{ji}$ ($i\lt j$), $E_{ii}$ / $E_{ij}$ ($i\le j$) |
| skew-symmetric $n\times n$ | $\tfrac{n(n-1)}2$ | $E_{ij}-E_{ji}$, $i\lt j$ |
| trace-zero $n\times n$ | $n^2-1$ | $E_{ij}$ ($i\ne j$), $E_{ii}-E_{nn}$ ($i\lt n$) |
| $\mathbb{C}^n$ over $\mathbb{R}$ | $2n$ | $e_k,\ ie_k$ |
| Hermitian $n\times n$, over $\mathbb{R}$ | $n^2$ | $E_{ii}$, $E_{ij}+E_{ji}$, $i(E_{ij}-E_{ji})$ ($i\lt j$) |
For a subspace cut out by conditions, the working rule is: dimension = (dimension of the big space) − (number of independent conditions). It is a consequence of the rank–nullity theorem (Theorem 3.6), since $k$ linear conditions on $V$ are the kernel of a linear map $V\to\mathbb{F}^k$, and "independent" means that map has rank $k$. The trap is conditions that look independent but are not.
Proof. Let $z_1,\dots,z_k$ be a basis of $U\cap W$. By Theorem 3.2(3) extend it to a basis $z_1,\dots,z_k,u_1,\dots,u_p$ of $U$ and to a basis $z_1,\dots,z_k,w_1,\dots,w_q$ of $W$. The $k+p+q$ vectors $z_i,u_j,w_l$ span $U+W$. They are independent: if $\sum a_iz_i+\sum b_ju_j+\sum c_lw_l=0$, the vector $\sum c_lw_l=-\sum a_iz_i-\sum b_ju_j$ lies in $U\cap W$, so it is $\sum d_iz_i$; independence of the basis of $W$ forces all $c_l=0$ (and $d_i=0$), and then independence of the basis of $U$ forces $a_i=b_j=0$. So $\dim(U+W)=k+p+q=(k+p)+(k+q)-k$.
If $U\cap W=\{0\}$ and $u+w=u'+w'$, then $u-u'=w'-w\in U\cap W$, so the decomposition is unique; conversely, a nonzero $v\in U\cap W$ gives $v=v+0=0+v$. The dimension criterion is now the formula. For a complement, extend a basis of $U$ to a basis of $V$; the added vectors span a complement. ∎
Two useful readings. In $\mathbb{R}^5$, two subspaces of dimension $3$ meet in at least a line, because $\dim(U\cap W)\ge3+3-5=1$. And complements are not unique: in $\mathbb{R}^2$ every line other than the $x$-axis is a complement of the $x$-axis.
Over a finite field everything is finite, so dimension becomes counting. GATE asks for the number of vectors, bases, invertible matrices or subspaces.
- $|V|=q^n$;
- the number of ordered bases of $V$, which is also $|GL_n(\mathbb{F}_q)|$, the number of invertible $n\times n$ matrices over $\mathbb{F}_q$, is $(q^n-1)(q^n-q)(q^n-q^2)\cdots(q^n-q^{n-1})$;
- the number of $k$-dimensional subspaces of $V$ is the Gaussian binomial coefficient $$\binom nk_q=\frac{(q^n-1)(q^n-q)\cdots(q^n-q^{k-1})}{(q^k-1)(q^k-q)\cdots(q^k-q^{k-1})},$$ and $\binom nk_q=\binom n{n-k}_q$. In particular there are $\dfrac{q^n-1}{q-1}$ one-dimensional subspaces.
Proof. (1) A basis gives a bijection $V\to\mathbb{F}_q^n$, $v\mapsto[v]_{\mathcal{B}}$. (2) Build an ordered basis one vector at a time. $b_1$ is any nonzero vector: $q^n-1$ choices. Once $b_1,\dots,b_i$ are chosen (independent), $b_{i+1}$ must avoid their span, which has $q^i$ elements: $q^n-q^i$ choices. By Theorem 3.2(3) the process yields exactly the ordered bases. An invertible matrix is the same as an ordered basis of $\mathbb{F}_q^n$ (its columns). (3) The same argument counts ordered $k$-tuples of independent vectors: $(q^n-1)\cdots(q^n-q^{k-1})$. Each $k$-dimensional subspace arises from exactly as many such tuples as it has ordered bases, namely $(q^k-1)\cdots(q^k-q^{k-1})$ by (2); divide. The symmetry follows because, for $V=\mathbb{F}_q^n$, the map $W\mapsto W^{\perp}=\{x:x\cdot w=0\ \forall w\in W\}$ is a bijection from $k$-dimensional to $(n-k)$-dimensional subspaces (it is its own inverse, and $\dim W^\perp=n-k$ by rank–nullity); alternatively, simplify the formula. ∎
Linear Maps, Kernel, Image and Rank–Nullity
Proof. The formula is well defined because coordinates are unique, and it is linear because coordinates of $u+cv$ are those of $u$ plus $c$ times those of $v$. Any linear $T$ with $Tb_i=w_i$ must satisfy the formula, by linearity. The image is the set of all $\sum a_iw_i$. ∎
So to decide whether a linear map with prescribed values exists, check whether the prescribed vectors are independent; if they are not, the prescribed values must satisfy the same relations.
Proof. Let $u_1,\dots,u_k$ be a basis of $\ker T$ and extend it to a basis $u_1,\dots,u_k,v_1,\dots,v_r$ of $V$ (Theorem 3.2), so $\dim V=k+r$. We show that $Tv_1,\dots,Tv_r$ is a basis of $\operatorname{im}T$. Spanning: any $v\in V$ is $\sum a_iu_i+\sum c_jv_j$, so $Tv=\sum c_jTv_j$ because $Tu_i=0$. Independence: if $\sum c_jTv_j=0$, then $T\left(\sum c_jv_j\right)=0$, so $\sum c_jv_j\in\ker T$ and $\sum c_jv_j=\sum a_iu_i$ for some $a_i$; independence of the whole basis gives all $c_j=0$. Hence $\operatorname{rank}T=r=\dim V-\operatorname{nullity}T$. ∎
- $T$ is injective if and only if $\ker T=\{0\}$.
- If $T$ is injective then $\dim V\le\dim W$; if $T$ is surjective then $\dim V\ge\dim W$. Conversely, if $\dim V\le\dim W$ an injective linear map $V\to W$ exists, and if $\dim V\ge\dim W$ a surjective one exists.
- If $\dim V=\dim W$, then $T$ is injective $\iff$ $T$ is surjective $\iff$ $T$ is an isomorphism. In particular, for $S,T\in\mathcal{L}(V)$, $ST=I$ implies $TS=I$.
- $V\cong W$ (isomorphic) if and only if $\dim V=\dim W$; so every $n$-dimensional space over $\mathbb{F}$ is isomorphic to $\mathbb{F}^n$, and $\dim\mathcal{L}(V,W)=\dim V\cdot\dim W$.
- For linear $S:U\to V$ and $T:V\to W$: $\operatorname{rank}(TS)\le\min(\operatorname{rank}S,\operatorname{rank}T)$.
Proof. (1) $Tu=Tv\iff T(u-v)=0$. (2) Injective means nullity $0$, so $\dim V=\operatorname{rank}T\le\dim W$; surjective means rank $=\dim W$, so $\dim V=\dim W+\operatorname{nullity}T\ge\dim W$. For the converses, send a basis of $V$ to independent vectors of $W$, respectively onto a spanning set of $W$ (sending the surplus basis vectors to $0$), using Theorem 3.5. (3) With $\dim V=\dim W=n$: injective $\iff$ nullity $0$ $\iff$ rank $n$ $\iff$ surjective. If $ST=I$ then $T$ is injective ($Tv=0\Rightarrow v=STv=0$), hence bijective, and $S=S(TT^{-1})=(ST)T^{-1}=T^{-1}$, so $TS=I$. (4) If $\dim V=\dim W$, send a basis to a basis. Fixing bases identifies $\mathcal{L}(V,W)$ with $M_{m\times n}(\mathbb{F})$ (Theorem 3.8 below), of dimension $mn$. (5) $\operatorname{im}(TS)=T(\operatorname{im}S)$ is the image of $\operatorname{im}S$ under $T$, so its dimension is at most $\dim\operatorname{im}S$ (rank–nullity for $T$ restricted to $\operatorname{im}S$), and it is contained in $\operatorname{im}T$. ∎
Matrices of Linear Maps and Change of Basis
- $[Tv]_{\mathcal{C}}=[T]_{\mathcal{B}}^{\mathcal{C}}\,[v]_{\mathcal{B}}$ for every $v\in V$;
- if $\mathcal{D}$ is a basis of a third space $U$ and $S\in\mathcal{L}(W,U)$, then $[S\circ T]_{\mathcal{B}}^{\mathcal{D}}=[S]_{\mathcal{C}}^{\mathcal{D}}\,[T]_{\mathcal{B}}^{\mathcal{C}}$;
- $T\mapsto[T]_{\mathcal{B}}^{\mathcal{C}}$ is an isomorphism $\mathcal{L}(V,W)\to M_{m\times n}(\mathbb{F})$;
- $\operatorname{rank}T=\operatorname{rank}[T]_{\mathcal{B}}^{\mathcal{C}}$ and $\operatorname{nullity}T=n-\operatorname{rank}[T]_{\mathcal{B}}^{\mathcal{C}}$; for $T\in\mathcal{L}(V)$, $T$ is invertible iff $[T]_{\mathcal{B}}$ is, and $[T^{-1}]_{\mathcal{B}}=[T]_{\mathcal{B}}^{-1}$.
Proof. (1) If $v=\sum_jx_jb_j$ then $Tv=\sum_jx_j\sum_ia_{ij}c_i=\sum_i\left(\sum_ja_{ij}x_j\right)c_i$, whose coordinate vector is $(a_{ij})(x_j)$. (2) Apply (1) twice: $[STv]_{\mathcal{D}}=[S]\,[Tv]_{\mathcal{C}}=[S]\,[T]\,[v]_{\mathcal{B}}$ for every $v$; taking $v=b_j$ compares the $j$-th columns. (3) The map is linear and, by Theorem 3.5, bijective (any matrix prescribes the images of the $b_j$). (4) The coordinate maps are isomorphisms carrying $\operatorname{im}T$ onto the column space of the matrix and $\ker T$ onto its null space. The last claim follows from (2) with $S=T^{-1}$. ∎
Proof. $T=I_W\circ T\circ I_V$; Theorem 3.8(2) with the bases $\mathcal{B}'\to\mathcal{B}\to\mathcal{C}\to\mathcal{C}'$ gives $[T]_{\mathcal{B}'}^{\mathcal{C}'}=[I]_{\mathcal{C}}^{\mathcal{C}'}[T]_{\mathcal{B}}^{\mathcal{C}}[I]_{\mathcal{B}'}^{\mathcal{B}}=Q^{-1}[T]_{\mathcal{B}}^{\mathcal{C}}P$. The first formula is the case $W=V$, $\mathcal{C}=\mathcal{B}$, $\mathcal{C}'=\mathcal{B}'$. Conversely, if $B=P^{-1}[T]_{\mathcal{B}}P$, the columns of $P$ are the $\mathcal{B}$-coordinates of a new basis $\mathcal{B}'$, and $B=[T]_{\mathcal{B}'}$. In words: to apply $T$ in new coordinates, convert to old coordinates ($P$), apply $T$ there, and convert back ($P^{-1}$). ∎
- $\operatorname{tr}(AB)=\operatorname{tr}(BA)$ for $A\in M_{m\times n}$, $B\in M_{n\times m}$. Similar matrices have the same rank, trace, determinant, characteristic polynomial and eigenvalues (Section 3.2); so these are well defined for an operator $T\in\mathcal{L}(V)$.
- Every $A\in M_{m\times n}(\mathbb{F})$ of rank $r$ is equivalent to $\begin{pmatrix}I_r&0\\0&0\end{pmatrix}$ (the rank normal form). Hence two $m\times n$ matrices are equivalent if and only if they have the same rank.
Proof. (1) $\operatorname{tr}(AB)=\sum_i\sum_ja_{ij}b_{ji}=\sum_j\sum_ib_{ji}a_{ij}=\operatorname{tr}(BA)$. Then $\operatorname{tr}(P^{-1}AP)=\operatorname{tr}(APP^{-1})=\operatorname{tr}A$, $\det(P^{-1}AP)=\det P^{-1}\det A\det P=\det A$, and $\operatorname{rank}(P^{-1}AP)=\operatorname{rank}A$ because multiplying by invertible matrices does not change the dimension of the image. For the characteristic polynomial, $xI-P^{-1}AP=P^{-1}(xI-A)P$. (2) Regard $A$ as $T:\mathbb{F}^n\to\mathbb{F}^m$. Choose a basis $u_1,\dots,u_k$ of $\ker T$ ($k=n-r$) and extend it to a basis $v_1,\dots,v_r,u_1,\dots,u_k$ of $\mathbb{F}^n$. By the proof of Theorem 3.6, $Tv_1,\dots,Tv_r$ is a basis of $\operatorname{im}T$; extend it to a basis of $\mathbb{F}^m$. In these bases $Tv_i$ is the $i$-th basis vector and $Tu_j=0$, so the matrix is the rank normal form, and by Theorem 3.9 it equals $Q^{-1}AP$. Two matrices of the same rank are both equivalent to the same normal form, hence to each other; equivalent matrices have equal rank. ∎
Rank and Systems of Linear Equations
The elementary row operations on a matrix are: swap two rows; multiply a row by a nonzero scalar; add a multiple of one row to another. Each is left multiplication by an invertible elementary matrix (the result of applying the operation to $I$). A matrix is in row echelon form if the zero rows are at the bottom and the first nonzero entry (pivot) of each row lies strictly to the right of the pivot of the row above; it is in reduced row echelon form (RREF) if, in addition, every pivot is $1$ and is the only nonzero entry of its column.
For $A\in M_{m\times n}(\mathbb{F})$: the row space $R(A)\subseteq\mathbb{F}^n$ is the span of the rows, the column space $C(A)=\operatorname{im}A\subseteq\mathbb{F}^m$ the span of the columns, and the null space $N(A)=\ker A=\{x:Ax=0\}$. The rank of $A$ is $\dim C(A)$.
- Row operations do not change the row space or the null space of $A$, and they preserve every linear relation among the columns: $\sum c_j(\text{col}_jA)=0\iff\sum c_j(\text{col}_jEA)=0$. (They do change the column space in general.)
- Every matrix can be brought to RREF by row operations (Gauss–Jordan elimination), and the RREF is unique.
- If the RREF of $A$ has $r$ pivots, then the $r$ nonzero rows of the RREF are a basis of $R(A)$, the $r$ pivot columns of $A$ (not of the RREF) are a basis of $C(A)$, and the free variables give a basis of $N(A)$ with $n-r$ vectors. Hence $$\dim R(A)=\dim C(A)=\operatorname{rank}A,\qquad\operatorname{rank}A=\operatorname{rank}A^{\mathsf T}.$$
- $\operatorname{rank}A$ is the largest $k$ such that $A$ has a nonzero $k\times k$ minor.
Proof. (1) If $E$ is invertible, the rows of $EA$ are combinations of the rows of $A$ and conversely (use $E^{-1}$), so $R(EA)=R(A)$; and $Ax=0\iff EAx=0$, which is the statement about relations among columns (a relation $\sum c_j\,\text{col}_j=0$ is exactly $Ac=0$). (2) Existence: scan the columns from the left; in the first column with a nonzero entry below the current row, swap it up, scale it to $1$ and clear the rest of its column; continue with the next row. Uniqueness is a careful induction on the number of columns (see the 📚 box). (3) In the RREF $R$, the nonzero rows are independent (each has a $1$ in a pivot column where the others have $0$), and they span $R(R)=R(A)$. The pivot columns of $R$ are distinct standard basis vectors, and every non-pivot column of $R$ is a combination of the pivot columns to its left; by (1) the same relations hold among the columns of $A$, so the pivot columns of $A$ form a basis of $C(A)$. Both spaces therefore have dimension $r$; and $R(A)=C(A^{\mathsf T})$. Solving $Rx=0$ for the pivot variables in terms of the $n-r$ free ones gives a basis of $N(A)$. (4) A nonzero $k\times k$ minor gives $k$ independent rows of a $k\times k$ submatrix, hence $k$ independent rows of $A$, so $k\le\operatorname{rank}A$. Conversely choose $r$ independent rows; the $r\times n$ matrix they form has column rank $r$ by (3), so some $r$ of its columns are independent, and the $r\times r$ submatrix they cut out is invertible. ∎
- $\operatorname{rank}(AB)\le\min(\operatorname{rank}A,\operatorname{rank}B)$; and $\operatorname{rank}(QAP)=\operatorname{rank}A$ for invertible $Q,P$.
- $\operatorname{rank}(A+C)\le\operatorname{rank}A+\operatorname{rank}C$ for $C\in M_{m\times n}$.
- Sylvester's inequality: $\operatorname{rank}A+\operatorname{rank}B-n\le\operatorname{rank}(AB)$. In particular $AB=0$ implies $\operatorname{rank}A+\operatorname{rank}B\le n$.
- For real $A$: $\operatorname{rank}(A^{\mathsf T}A)=\operatorname{rank}(AA^{\mathsf T})=\operatorname{rank}A$. For complex $A$ the same holds with the conjugate transpose $A^*$ in place of $A^{\mathsf T}$ (but not with $A^{\mathsf T}$).
- $\operatorname{rank}A\le\min(m,n)$; a square matrix is invertible iff it has full rank.
- $\operatorname{rank}A=1$ if and only if $A=uv^{\mathsf T}$ for nonzero $u\in\mathbb{F}^m$, $v\in\mathbb{F}^n$.
Proof. (1) is Theorem 3.7(5); applying it twice, $\operatorname{rank}(QAP)\le\operatorname{rank}A$ and $\operatorname{rank}A=\operatorname{rank}\left(Q^{-1}(QAP)P^{-1}\right)\le\operatorname{rank}(QAP)$. (2) $C(A+C)\subseteq C(A)+C(C)$, and $\dim(U+W)\le\dim U+\dim W$. (3) Restrict $A$ to the subspace $C(B)$: the image of $A|_{C(B)}$ is $C(AB)$ and its kernel is $C(B)\cap N(A)$, so by rank–nullity
$$\operatorname{rank}(AB)=\operatorname{rank}B-\dim\big(C(B)\cap N(A)\big)\ge\operatorname{rank}B-\dim N(A),$$and $\dim N(A)=n-\operatorname{rank}A$. (4) If $A^{\mathsf T}Ax=0$ then $0=x^{\mathsf T}A^{\mathsf T}Ax=\|Ax\|^2$, so $Ax=0$; thus $N(A^{\mathsf T}A)=N(A)$, and both matrices have $n$ columns, so rank–nullity gives equal ranks. Apply this to $A^{\mathsf T}$ for $AA^{\mathsf T}$. Over $\mathbb{C}$ use $x^*A^*Ax=\|Ax\|^2$; with the plain transpose the argument breaks, see the ⚠️ box. (5) is Theorem 3.11 and Theorem 3.7(3). (6) If $\operatorname{rank}A=1$, the column space is a line $\operatorname{span}\{u\}$, so column $j$ is $v_ju$ for some scalars $v_j$, not all zero: $A=uv^{\mathsf T}$. Conversely every column of $uv^{\mathsf T}$ is a multiple of $u\ne0$ and some column is nonzero. ∎
- $Ax=b$ has a solution if and only if $\operatorname{rank}A=\operatorname{rank}[A\,|\,b]$.
- If $x_p$ is one solution, the set of all solutions is $x_p+N(A)=\{x_p+h:Ah=0\}$, a translate of a subspace of dimension $n-r$.
- Hence exactly one of the following holds: no solution ($\operatorname{rank}[A\,|\,b]=r+1$); exactly one solution ($\operatorname{rank}[A\,|\,b]=r=n$); infinitely many solutions over $\mathbb{R}$ or $\mathbb{C}$, described by $n-r$ free parameters ($\operatorname{rank}[A\,|\,b]=r\lt n$).
- A homogeneous system with more unknowns than equations ($m\lt n$) has a nontrivial solution. If $m=n$, $Ax=b$ is uniquely solvable for every $b$ iff $Ax=0$ has only the trivial solution.
Proof. (1) $Ax=x_1\,\text{col}_1+\cdots+x_n\,\text{col}_n$, so $Ax=b$ is solvable iff $b\in C(A)$, iff adding $b$ as a column does not increase the dimension of the column space. (2) If $Ax_p=b$, then $Ax=b\iff A(x-x_p)=0$. (3) Adding one column raises the rank by $0$ or $1$; combine (1), (2) and $\dim N(A)=n-r$; a subspace of positive dimension over an infinite field has infinitely many vectors. (4) $r\le m\lt n$ gives $\dim N(A)\gt0$; for $m=n$ use Theorem 3.7(3). ∎
For $A\in M_n(\mathbb{F})$ the following are equivalent: $A$ is invertible; $\det A\ne0$; $\operatorname{rank}A=n$; $N(A)=\{0\}$; $Ax=b$ has a unique solution for every $b$; the columns (equivalently, the rows) form a basis of $\mathbb{F}^n$; the RREF of $A$ is $I$; $A$ is a product of elementary matrices; $0$ is not an eigenvalue of $A$.
Cramer's rule. If $\det A\ne0$, the unique solution of $Ax=b$ is $x_i=\dfrac{\det A_i}{\det A}$, where $A_i$ is $A$ with its $i$-th column replaced by $b$.
Proof. Rank $n$, trivial null space, unique solvability and "columns form a basis" are equivalent by rank–nullity and Theorem 3.13. If the rank is $n$ the RREF has $n$ pivots, so it is $I$, and $E_k\cdots E_1A=I$ exhibits $A$ as a product of elementary matrices (their inverses) and as invertible. Since elementary matrices have nonzero determinants and $\det(XY)=\det X\det Y$, $\det A\ne0$ iff the RREF has nonzero determinant iff it is $I$. Finally $0$ is an eigenvalue iff $Ax=0$ for some $x\ne0$. For Cramer's rule, let $X_i$ be $I$ with its $i$-th column replaced by $x$; then $AX_i=A_i$ (column $i$ becomes $Ax=b$, the others $Ae_j$), and $\det X_i=x_i$ (expand along row $i$). Taking determinants, $\det A\cdot x_i=\det A_i$. ∎
- Row reduce the augmented matrix, keeping the parameters in the last rows; never divide by an expression that might be $0$.
- Read off the last nonzero row of the coefficient part, typically $(\text{expression in }\lambda)\,z=(\text{expression in }\mu)$.
- Coefficient $\ne0$: rank $n$, unique solution. Coefficient $=0$ and right side $\ne0$: ranks differ, no solution. Both $0$: ranks equal and $\lt n$, infinitely many solutions with $n-r$ parameters.
- For a square system, the shortcut "$\det A\ne0\iff$ unique" decides the first case at once; but $\det A=0$ alone never tells you whether there are no solutions or infinitely many.
- A union of subspaces is usually not a subspace. The union of the two axes in $\mathbb{R}^2$ contains $(1,0)$ and $(0,1)$ but not their sum (Theorem 3.1(3)).
- Familiar sets that are not subspaces: singular $n\times n$ matrices ($\operatorname{diag}(1,0)+\operatorname{diag}(0,1)=I$); invertible matrices ($0$ is missing); polynomials of degree exactly $n$ (the sum $x^n+(1-x^n)$ has degree $0$); idempotent matrices ($I+I=2I$ is not idempotent); $\{x\in\mathbb{R}^2:x_1x_2\ge0\}$.
- The scalars change the dimension. $\dim_{\mathbb{C}}\mathbb{C}^n=n$ but $\dim_{\mathbb{R}}\mathbb{C}^n=2n$. Hermitian matrices form a real space of dimension $n^2$ that is not a complex subspace ($iH$ is skew-Hermitian).
- Conditions that look independent may not be. "All row sums and all column sums are $0$" is six conditions on $M_3(\mathbb{R})$, but they have rank $5$ (the three row sums and the three column sums both add up to the sum of all entries), so the dimension is $9-5=4$, not $3$.
- No inclusion–exclusion for three subspaces. Three distinct lines $U,V,W$ through $0$ in $\mathbb{R}^2$: all intersections are $\{0\}$, but $\dim(U+V+W)=2\ne1+1+1$. For the same reason, pairwise trivial intersections do not make $U+V+W$ direct.
- Over a finite field, a space can be a union of proper subspaces. $\mathbb{F}_2^2$ is the union of its three lines. Over $\mathbb{R}$ or $\mathbb{C}$ this never happens.
- $\ker T=\operatorname{im}T$ forces $\dim V$ even (Example 4(a)).
- Injective $\iff$ surjective only for maps between spaces of the same finite dimension. On $\mathbb{R}[x]$, $p\mapsto p'$ is surjective but not injective, and $p\mapsto xp$ is injective but not surjective.
- Same rank, trace, determinant and characteristic polynomial do not give similarity: $I_2$ versus $\begin{pmatrix}1&1\\0&1\end{pmatrix}$. Same rank does give equivalence ($QAP$), a much weaker relation.
- $\operatorname{rank}(AB)\ne\operatorname{rank}(BA)$ in general. $A=\begin{pmatrix}0&1\\0&0\end{pmatrix}$, $B=\begin{pmatrix}1&0\\0&0\end{pmatrix}$: $AB=0$ but $BA=A$ has rank $1$.
- $\operatorname{rank}(A^{\mathsf T}A)=\operatorname{rank}A$ is a real fact. For $A=\begin{pmatrix}1\\i\end{pmatrix}$, $A^{\mathsf T}A=1+i^2=0$ although $\operatorname{rank}A=1$; the correct complex statement uses $A^*A=2$.
- Row operations change the column space. $\begin{pmatrix}1&1\\1&1\end{pmatrix}$ has column space $\operatorname{span}\{(1,1)\}$; its RREF $\begin{pmatrix}1&1\\0&0\end{pmatrix}$ has column space $\operatorname{span}\{(1,0)\}$. Take the pivot columns of the original matrix.
- $\det A=0$ does not mean "no solution". It means "not exactly one": compare the two ranks (Example 6 with $\lambda=2$). Cramer's rule needs $\det A\ne0$.
- CSIR Unit 1 · §8.1 Vector Spaces, Bases and Dimension — the Steinitz exchange theorem in full, bases of infinite-dimensional spaces, why a space over an infinite field is never a finite union of proper subspaces, quotient spaces $V/W$ and their dimension, and the complete counting proofs over $\mathbb{F}_q$.
- CSIR Unit 1 · §8.2 Linear Transformations and Their Matrices — the first isomorphism theorem, the algebra $\mathcal{L}(V)$, the rank normal form, dual spaces and annihilators, projections and direct sums, and the structure of nilpotent maps.
- CSIR Unit 1 · §8.3 Rank, Determinants and Linear Equations — uniqueness of the RREF, rank factorisation, the Frobenius and Sylvester inequalities, the determinant from its axioms, Laplace expansion, the adjugate, block determinants, and the Rouché–Capelli theorem with full proofs.
Two Labs
Exercises
- 1 Show that $W=\{(x,y,z)\in\mathbb{R}^3:x+2y=z,\ 2x=y\}$ is a subspace and find a basis and its dimension.
- 2 Is the set of singular $2\times2$ real matrices a subspace of $M_2(\mathbb{R})$? Is the set of $2\times2$ real matrices with $a_{11}=a_{22}$?
- 3 Find the dimensions of the space of real skew-symmetric $n\times n$ matrices and of the space of upper triangular $n\times n$ matrices with trace $0$.
- 4 Find a basis of $W=\{p\in P_3(\mathbb{R}):p(0)=p(2),\ p'(1)=0\}$.
- 5 Show that $(1,1,0),(1,0,1),(0,1,1)$ is a basis of $\mathbb{R}^3$ and find the coordinates of $(2,3,5)$ in it. Is it a basis of $\mathbb{F}_2^3$?
- 6 In $\mathbb{R}^4$ let $U=\{x:x_1=x_2\}$ and $W=\{x:x_3=x_4,\ x_1+x_2+x_3=0\}$. Find $\dim U$, $\dim W$, $\dim(U\cap W)$ and $\dim(U+W)$. Is the sum direct?
- 7 How many $3$-dimensional subspaces does $\mathbb{F}_2^5$ have? How many vectors of $\mathbb{F}_2^5$ lie outside a given $3$-dimensional subspace?
- 8 Show that a real vector space is never the union of two proper subspaces, and find three proper subspaces of $\mathbb{F}_2^2$ whose union is $\mathbb{F}_2^2$.
- 9 Regard $V=\mathbb{C}^2$ as a real vector space. Give a basis and $\dim_{\mathbb{R}}V$. Is $\{(z,\bar z):z\in\mathbb{C}\}$ a real subspace? A complex subspace?
- 1 $T:\mathbb{R}^3\to\mathbb{R}^3$, $T(x,y,z)=(x-y,\ y-z,\ z-x)$. Find $\ker T$, $\operatorname{im}T$ and the rank.
- 2 Let $D:P_n(\mathbb{R})\to P_n(\mathbb{R})$ be differentiation. Find its rank and nullity and the least $k$ with $D^k=0$.
- 3 $T:M_n(\mathbb{R})\to M_n(\mathbb{R})$, $T(A)=A+A^{\mathsf T}$. Identify $\ker T$ and $\operatorname{im}T$ and check rank–nullity.
- 4 Find the nullity of the trace map $M_n(\mathbb{F})\to\mathbb{F}$.
- 5 Is there a linear map $T:\mathbb{R}^3\to\mathbb{R}^3$ with $T(1,1,0)=(1,0,0)$, $T(0,1,1)=(0,1,0)$ and $T(1,2,1)=(1,1,1)$?
- 6 $T:V\to W$ is linear with $\dim V=7$, $\dim W=4$. Show that $\operatorname{nullity}T\ge3$. Can $T$ be injective? Must it be surjective?
- 7 Let $T\in\mathcal{L}(\mathbb{R}^n)$ with $\operatorname{rank}T^2=\operatorname{rank}T$. Prove that $\mathbb{R}^n=\ker T\oplus\operatorname{im}T$.
- 8 Let $T\in\mathcal{L}(\mathbb{R}^n)$ with $T^2=T$. Prove that $\mathbb{R}^n=\ker T\oplus\operatorname{im}T$ and $\operatorname{rank}T+\operatorname{rank}(I-T)=n$.
- 9 On the space $\mathbb{R}[x]$ of all real polynomials, give a linear map that is injective but not surjective and one that is surjective but not injective. Why does this not contradict Theorem 3.7(3)?
- 1 Find the matrix of $D:P_3(\mathbb{R})\to P_2(\mathbb{R})$, $D(p)=p'$, relative to $(1,x,x^2,x^3)$ and $(1,x,x^2)$, and its rank.
- 2 $T(x,y)=(2x+y,\ x-y)$. Find $[T]_{\mathcal{B}}$ for $\mathcal{B}=((1,1),(1,-1))$, and check that it has the same trace and determinant as the standard matrix.
- 3 Find the matrix of the transpose map $X\mapsto X^{\mathsf T}$ on $M_2(\mathbb{R})$ relative to $(E_{11},E_{12},E_{21},E_{22})$, and its trace and determinant. Explain the trace using symmetric and skew-symmetric matrices.
- 4 Show that there are no $A,B\in M_n(\mathbb{R})$ with $AB-BA=I$.
- 5 Are $\begin{pmatrix}1&2\\2&4\end{pmatrix}$ and $\begin{pmatrix}5&0\\0&0\end{pmatrix}$ similar? Are $\begin{pmatrix}1&2\\2&4\end{pmatrix}$ and $\begin{pmatrix}0&5\\0&0\end{pmatrix}$ similar? Equivalent?
- 6 $\mathcal{B}=(b_1,b_2,b_3)$ is a basis of $V$ and $\mathcal{B}'=(b_1,\ b_1+b_2,\ b_1+b_2+b_3)$. Find the transition matrix $P$ from $\mathcal{B}'$ to $\mathcal{B}$ and its inverse, and find $[v]_{\mathcal{B}'}$ when $[v]_{\mathcal{B}}=(1,2,3)^{\mathsf T}$.
- 7 How many equivalence classes (under $A\sim QAP$) are there in $M_{3\times4}(\mathbb{R})$?
- 8 Show that $\begin{pmatrix}1&1\\0&1\end{pmatrix}$ and $\begin{pmatrix}1&0\\1&1\end{pmatrix}$ are similar, with an explicit $P$.
- 1 Find the rank of the $4\times4$ matrix with entries $a_{ij}=i+j-1$.
- 2 For which $k$ does $\begin{pmatrix}1&1&1\\1&k&1\\1&1&k\end{pmatrix}$ have rank $1$, $2$, $3$?
- 3 For which $t$ is the system $x+y+z=1$, $2x+3y+z=t$, $4x+7y+z=t^2$ consistent? Solve it in each such case.
- 4 Let $A$ be a $3\times5$ real matrix of rank $3$. Show that $Ax=b$ is solvable for every $b\in\mathbb{R}^3$ and describe the solution set.
- 5 Solve $2x+y-z=1$, $x-y+2z=4$, $3x+2y+z=5$ by Cramer's rule.
- 6 Prove that $\operatorname{rank}(A^{\mathsf T}A)=\operatorname{rank}A$ for every real matrix $A$, and give a complex matrix for which it fails.
- 7 Let $A,B\in M_n(\mathbb{R})$ with $AB=0$. Show that $\operatorname{rank}A+\operatorname{rank}B\le n$, and give an example in $M_4(\mathbb{R})$ with equality and both matrices nonzero.
- 8 Modelling. Four junctions $A,B,C,D$ lie clockwise round a city block, joined by one-way streets $A\to B$, $B\to C$, $C\to D$, $D\to A$ carrying $x_1,x_2,x_3,x_4$ vehicles per hour. $400$ vehicles/h enter at $A$, $150$/h enter at $C$, $250$/h leave at $B$ and $300$/h leave at $D$. Write the balance equations (flow in = flow out at each junction), find the rank of the system and its general solution, and find the smallest possible flow on each street if all flows must be non-negative.
E1. GATE MA · MCQ Let $W=\{p\in P_5(\mathbb{R}):p(1)=p(-1),\ p(2)=p(-2),\ p(3)=p(-3),\ p'(0)=0\}$. Then $\dim W$ is (A) $2$; (B) $3$; (C) $4$; (D) $1$.
E2. GATE MA · MCQ The system $x+y+2z=2$, $2x+3y+z=1$, $3x+4y+az=b$ has infinitely many solutions if and only if (A) $a=3,\ b=3$; (B) $a=3,\ b\ne3$; (C) $a\ne3$; (D) $a=6,\ b=6$.
E3. GATE MA · MSQ Let $A$ be a real $5\times3$ matrix and $B$ a real $3\times5$ matrix. Which of the following is/are true? (One or more options may be correct.) (A) $\det(AB)=0$. (B) $\det(BA)=0$. (C) If $\operatorname{rank}A=3$ then $A^{\mathsf T}A$ is invertible. (D) If $AB=0$ then $\operatorname{rank}A+\operatorname{rank}B\le3$.
E4. GATE MA · MSQ Which of the following subsets of $M_3(\mathbb{R})$ is/are subspaces? (One or more options may be correct.) (A) $\{A:\operatorname{tr}A=0\}$. (B) $\{A:\det A=0\}$. (C) $\{A:A^{\mathsf T}=2A\}$. (D) $\{A:Av=0\}$ for a fixed $v\in\mathbb{R}^3$.
E5. GATE MA · NAT The number of $2$-dimensional subspaces of the vector space $\mathbb{F}_3^4$ over the field with three elements is ______.
E6. GATE MA · NAT Let $A$ be the $6\times6$ real matrix with entries $a_{ij}=(i+j)^2$. The dimension of the solution space of $Ax=0$ is ______.
Suggested plan — 3 lectures × 60 min.
- Spaces and dimension. Definitions 3.1–3.3, Theorem 3.1 (prove the union statement on the board — it is a favourite MSQ option), Theorem 3.2 with the elimination proof of the exchange inequality, the table of standard dimensions, and Example 1 as a timed drill. Then Theorem 3.3 and the counting Theorem 3.4 with Example 2.
- Linear maps. Definition 3.5, Theorems 3.5–3.7 with the full rank–nullity proof, Examples 3 and 4 (let the class vote on each part of Example 4 before you reveal it). Project Interactive 1: run the two rank-one matrices and ask students to predict the kernel and image lines before $t$ reaches $1$.
- Matrices and systems. Definitions 3.6–3.7 and Theorems 3.8–3.10; Example 5 shows that a change of basis can turn a full matrix into a Jordan block — a hook for Section 3.2. Then Theorems 3.11–3.13, the strategy box, Examples 6 and 7. Project Interactive 2 and ask: which points of the parameter plane give infinitely many solutions, and why only one point? Finish with GATE corner E1 and E3.
Discussion questions. (1) Why must $\ker T=\operatorname{im}T$ fail in odd dimension, and what does the smallest example in dimension $2$ look like? (2) "Similar matrices have the same rank, trace and determinant." Which of these survive for equivalent matrices $QAP$, and why is equivalence so much coarser? (3) In Example 6, the line $\lambda=2$ of the parameter plane is "almost all bad". What is special about the one good point $(2,5)$ in terms of the column space?
Misconceptions to watch for. Counting conditions without checking their independence; taking the pivot columns of the RREF instead of the original matrix as a basis of the column space; reading $\det A=0$ as "no solution"; using $\operatorname{rank}(A^{\mathsf T}A)=\operatorname{rank}A$ over $\mathbb{C}$; assuming injective $\Rightarrow$ surjective in infinite dimension; confusing the transition matrix $P$ with $P^{-1}$ (write "new in terms of old" as the columns of $P$).
Suggested homework. I(3, 4, 6, 7, 9), II(1, 3, 5, 7, 8), III(2, 3, 5, 6), IV(2, 3, 5, 7, 8); GATE corner E2, E4, E5.
Research question. How can a message of $4$ bits be protected so that any single bit flipped in transmission is detected and corrected — and why is the answer a subspace of $\mathbb{F}_2^7$ defined by a rank-$3$ matrix?
Why it matters. Error-correcting codes protect data in computer memory, on optical discs, in QR codes, in mobile networks and on deep-space probes, whose faint signals arrive with many corrupted bits. The simplest such code, the Hamming code, is pure linear algebra over $\mathbb{F}_2$: the valid codewords form the null space of a parity-check matrix $H$, rank–nullity gives the number of codewords, and the column structure of $H$ decides how many errors can be corrected.
What to do.
- Let $H$ be the $3\times7$ matrix over $\mathbb{F}_2$ whose $j$-th column is the binary expansion of $j$ ($j=1,\dots,7$). Show that $\operatorname{rank}H=3$ and conclude from Theorem 3.6 that the code $C=N(H)$ has dimension $4$ and $16$ codewords.
- Find a basis of $C$ (four codewords) by row reducing $H$ over $\mathbb{F}_2$, and write a $4$-bit message as a codeword using it.
- The weight of a word is its number of $1$'s. Show that no nonzero codeword has weight $1$ or $2$ (a codeword of weight $2$ would mean two equal columns of $H$). List the weights of all $16$ codewords.
- If a codeword $c$ is sent and $c+e_j$ is received (bit $j$ flipped), show that the syndrome $H(c+e_j)$ equals column $j$ of $H$ — the binary expansion of the position of the error. Write a short program that encodes, flips a random bit, and decodes.
Tools: pen and paper for steps 1–3; Python (or any language) with arithmetic modulo $2$ for step 4.
Hand in: the row reduction of $H$ and a basis of $C$; the table of weights; your encoder/decoder with three test messages; a paragraph explaining why two flipped bits are detected but mis-corrected.
Going further. The code $C$ is one of the $\binom74_2=11811$ four-dimensional subspaces of $\mathbb{F}_2^7$ (Theorem 3.4). Read about the extended Hamming code (add an overall parity bit) and about Reed–Solomon codes, which work over larger finite fields $\mathbb{F}_{2^8}$ and are used in QR codes.
🧪 Self-check quiz
Q1. The dimension of the real vector space of $4\times4$ real skew-symmetric matrices is
Q2. A linear map $T:\mathbb{R}^7\to\mathbb{R}^4$ is surjective. Its nullity is
Q3. For a $3\times3$ system $Ax=b$ with $\operatorname{rank}A=2$ and $\operatorname{rank}[A\,|\,b]=3$, the system has
Q4. The number of one-dimensional subspaces of $\mathbb{F}_2^3$ is
Q5. $A$ and $B$ are similar $n\times n$ matrices. Which of the following need not be equal?