Chapter 3 · Linear Algebra

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.

📘 Definition 3.1 — Vector space

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.

📘 Definition 3.2 — Subspace
A subset $W$ of a vector space $V$ is a subspace if it is a vector space under the same operations; equivalently, $0\in W$ and $W$ is closed under addition and scalar multiplication. $\{0\}$ and $V$ are the trivial subspaces.
📐 Theorem 3.1 — The subspace test; intersections and unions
  1. 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}$.
  2. Any intersection of subspaces is a subspace.
  3. 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. ∎

📘 Definition 3.3 — Span, linear independence, basis, dimension

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.

📐 Theorem 3.2 — The dimension theorem
  1. Exchange inequality. If $V$ is spanned by $n$ vectors, then every linearly independent subset of $V$ has at most $n$ vectors.
  2. Consequently any two bases of a finite-dimensional space have the same number of vectors.
  3. 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.
  4. 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)dimensiona 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.

✏️ Example 1 — Six dimensions
Find the dimension of each real vector space. (a) $W_1=\{p\in P_4(\mathbb{R}):p(1)=0,\ p'(1)=0\}$. (b) $W_2=\{A\in M_3(\mathbb{R}):A^{\mathsf T}=A,\ \operatorname{tr}A=0\}$. (c) $W_3=\{A\in M_3(\mathbb{R}):AD=DA\}$, where $D=\operatorname{diag}(1,1,2)$. (d) The set $W_4$ of $2\times2$ complex Hermitian matrices, as a real vector space; is it a complex subspace of $M_2(\mathbb{C})$? (e) $W_5=\{x\in\mathbb{R}^5:x_1+x_2+x_3+x_4+x_5=0,\ x_1=x_5\}$. (f) $W_6=\operatorname{span}\{(1,2,1,0),(2,1,0,1),(1,-1,-1,1),(4,5,2,1)\}$.
(a) $3$ $p(1)=p'(1)=0$ says $1$ is a root of multiplicity at least $2$, i.e. $p=(x-1)^2q$ with $q\in P_2(\mathbb{R})$. The map $q\mapsto(x-1)^2q$ is injective, so $\dim W_1=\dim P_2=3$, with basis $(x-1)^2,\ x(x-1)^2,\ x^2(x-1)^2$. (Two independent conditions on a space of dimension $5$.)
(b) $5$ Symmetric $3\times3$ matrices form a space of dimension $6$; $\operatorname{tr}A=0$ is one nonzero linear condition on it. $6-1=5$.
(c) $5$ $(AD-DA)_{ij}=a_{ij}(d_j-d_i)$. This vanishes automatically when $d_i=d_j$ and forces $a_{ij}=0$ when $d_i\ne d_j$. Here $d_1=d_2=1\ne d_3=2$, so $a_{13}=a_{23}=a_{31}=a_{32}=0$ and the other five entries are free: $W_3$ consists of the block matrices $\begin{pmatrix}B&0\\0&c\end{pmatrix}$ with $B\in M_2$, and $\dim W_3=4+1=5$.
(d) $4$; not complex $\begin{pmatrix}a&z\\\bar z&d\end{pmatrix}$ with $a,d\in\mathbb{R}$, $z\in\mathbb{C}$: four real parameters, basis $I,\ \operatorname{diag}(1,-1),\ \begin{pmatrix}0&1\\1&0\end{pmatrix},\ \begin{pmatrix}0&i\\-i&0\end{pmatrix}$. It is closed under real scalars but not complex ones: $iI$ is not Hermitian. So $W_4$ is a real subspace of $M_2(\mathbb{C})$ (viewed as a real space of dimension $8$), not a complex one.
(e) $3$ The two conditions have coefficient rows $(1,1,1,1,1)$ and $(1,0,0,0,-1)$, which are not proportional; $5-2=3$.
(f) $2$ Call the vectors $v_1,\dots,v_4$. Then $v_3=v_2-v_1$ and $v_4=2v_1+v_2$, while $v_1,v_2$ are not proportional. So $W_6=\operatorname{span}\{v_1,v_2\}$ and $\dim W_6=2$ — four vectors, but only two dimensions.
📘 Definition 3.4 — Sum and direct sum of subspaces
For subspaces $U,W\subseteq V$, the sum is $U+W=\{u+w:u\in U,\ w\in W\}$, the smallest subspace containing $U\cup W$. The sum is direct, written $U\oplus W$, if every vector of $U+W$ is $u+w$ in exactly one way; then $W$ is a complement of $U$ in $U\oplus W$. More generally $U_1+\cdots+U_k$ is direct if each of its vectors is $u_1+\cdots+u_k$ ($u_i\in U_i$) in exactly one way.
📐 Theorem 3.3 — The dimension formula (Grassmann)
Let $U,W$ be finite-dimensional subspaces of $V$. Then $$\dim(U+W)=\dim U+\dim W-\dim(U\cap W).$$ The sum $U+W$ is direct if and only if $U\cap W=\{0\}$, if and only if $\dim(U+W)=\dim U+\dim W$. Every subspace $U$ of a finite-dimensional $V$ has a complement, and every complement has dimension $\dim V-\dim U$.

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.

📐 Theorem 3.4 — Counting over a finite field
Let $V$ be a vector space of dimension $n$ over $\mathbb{F}_q$. Then:
  1. $|V|=q^n$;
  2. 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})$;
  3. 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. ∎

✏️ Example 2 — Counting over $\mathbb{F}_2$ and $\mathbb{F}_3$
(a) How many invertible $2\times2$ matrices are there over $\mathbb{F}_3$? (b) How many $2$-dimensional subspaces does $\mathbb{F}_2^4$ have? (c) How many lines through the origin (one-dimensional subspaces) and how many planes through the origin does $\mathbb{F}_3^3$ have? (d) How many $2\times2$ matrices over $\mathbb{F}_2$ have rank exactly $1$?
(a) $48$ $(3^2-1)(3^2-3)=8\cdot6=48$: a nonzero first column ($8$ ways), then a second column off its span ($9-3=6$ ways).
(b) $35$ $\binom42_2=\dfrac{(16-1)(16-2)}{(4-1)(4-2)}=\dfrac{15\cdot14}{3\cdot2}=35$.
(c) $13$ and $13$ Lines: $\dfrac{3^3-1}{3-1}=13$ (each line has $2$ nonzero vectors, and the $26$ nonzero vectors are shared out among the lines). Planes: $\binom32_3=\binom31_3=13$ by the symmetry.
(d) $9$ There are $2^4=16$ matrices; $|GL_2(\mathbb{F}_2)|=(4-1)(4-2)=6$ have rank $2$ and one (the zero matrix) has rank $0$. So $16-6-1=9$ have rank $1$. Check: a rank-$1$ matrix is $uv^{\mathsf T}$ with $u,v\ne0$ (Theorem 3.12(6)); there are $3\cdot3=9$ such pairs, and over $\mathbb{F}_2$ no two of them give the same matrix (the only nonzero scalar is $1$).

Linear Maps, Kernel, Image and Rank–Nullity

📘 Definition 3.5 — Linear map, kernel, image, rank, nullity
Let $V,W$ be vector spaces over $\mathbb{F}$. A map $T:V\to W$ is linear if $T(u+v)=Tu+Tv$ and $T(cv)=cTv$ for all $u,v\in V$, $c\in\mathbb{F}$. The set of linear maps is $\mathcal{L}(V,W)$, and $\mathcal{L}(V)=\mathcal{L}(V,V)$. The kernel (null space) is $\ker T=\{v:Tv=0\}$ and the image (range) is $\operatorname{im}T=\{Tv:v\in V\}$; both are subspaces (of $V$ and $W$). For finite-dimensional $V$, the nullity is $\dim\ker T$ and the rank is $\operatorname{rank}T=\dim\operatorname{im}T$. A bijective linear map is an isomorphism; its inverse is automatically linear.
📐 Theorem 3.5 — A linear map is determined by its values on a basis
Let $b_1,\dots,b_n$ be a basis of $V$ and let $w_1,\dots,w_n\in W$ be arbitrary. There is exactly one linear map $T:V\to W$ with $Tb_i=w_i$ for all $i$, namely $T\left(\sum a_ib_i\right)=\sum a_iw_i$. Moreover $\operatorname{im}T=\operatorname{span}\{w_1,\dots,w_n\}$.

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.

📐 Theorem 3.6 — The rank–nullity theorem
If $V$ is finite-dimensional and $T:V\to W$ is linear, then $\operatorname{im}T$ is finite-dimensional and $$\operatorname{rank}T+\operatorname{nullity}T=\dim V.$$

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$. ∎

📐 Theorem 3.7 — Consequences of rank–nullity
Let $V,W$ be finite-dimensional and $T\in\mathcal{L}(V,W)$.
  1. $T$ is injective if and only if $\ker T=\{0\}$.
  2. 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.
  3. 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$.
  4. $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$.
  5. 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$. ∎

✏️ Example 3 — Kernels and images
Find bases of the kernel and the image, and check rank–nullity. (a) $T:P_3(\mathbb{R})\to P_3(\mathbb{R})$, $T(p)=xp'(x)-2p(x)$. (b) $T:M_2(\mathbb{R})\to M_2(\mathbb{R})$, $T(X)=AX-XA$ with $A=\begin{pmatrix}1&1\\0&1\end{pmatrix}$. (c) $T:\mathbb{R}^4\to\mathbb{R}^3$, $Tx=Mx$ with $$M=\begin{pmatrix}1&2&0&1\\2&4&1&4\\1&2&1&3\end{pmatrix}.$$
(a) On the basis, $T(x^k)=kx^k-2x^k=(k-2)x^k$: so $T(1)=-2$, $T(x)=-x$, $T(x^2)=0$, $T(x^3)=x^3$. Kernel $\operatorname{span}\{x^2\}$, image $\operatorname{span}\{1,x,x^3\}$: $1+3=4=\dim P_3$.
(b) Write $A=I+N$ with $N=E_{12}$, so $T(X)=NX-XN$. For $X=\begin{pmatrix}p&q\\r&s\end{pmatrix}$, $NX-XN=\begin{pmatrix}r&s-p\\0&-r\end{pmatrix}$. Kernel: $r=0$, $s=p$, i.e. $X=pI+qN$, basis $\{I,N\}$, nullity $2$. Image: all $\begin{pmatrix}a&b\\0&-a\end{pmatrix}$, basis $\{E_{11}-E_{22},E_{12}\}$, rank $2$. $2+2=4=\dim M_2$.
(c) Row reduce $R_2-2R_1$ and $R_3-R_1$ both give $(0,0,1,2)$; subtracting, the echelon form has rows $(1,2,0,1)$, $(0,0,1,2)$, $(0,0,0,0)$. Rank $2$, pivots in columns $1$ and $3$.
(c) Bases Kernel: $x_1=-2x_2-x_4$, $x_3=-2x_4$ with $x_2,x_4$ free, so $\ker T=\operatorname{span}\{(-2,1,0,0),(-1,0,-2,1)\}$. Image: the pivot columns of $M$ itself, $(1,2,1)$ and $(0,1,1)$ (indeed column $2=2\cdot$column $1$ and column $4=$ column $1+2\cdot$column $3$). $2+2=4$. ✓
✏️ Example 4 — Prove or disprove
(a) There is a linear map $T:\mathbb{R}^5\to\mathbb{R}^5$ with $\ker T=\operatorname{im}T$. (b) There is a linear map $T:\mathbb{R}^4\to\mathbb{R}^4$ with $\ker T=\operatorname{im}T$. (c) If $T\in\mathcal{L}(\mathbb{R}^n)$ and $T^2=0$, then $\operatorname{rank}T\le n/2$. (d) There is an injective linear map $\mathbb{R}^3\to\mathbb{R}^2$. (e) If $S,T\in\mathcal{L}(V)$ satisfy $ST=I$, then $TS=I$.
(a) False $\ker T=\operatorname{im}T$ would give rank $=$ nullity $=r$, and $2r=5$ by rank–nullity — impossible.
(b) True Define $T$ on the standard basis by $Te_1=Te_2=0$, $Te_3=e_1$, $Te_4=e_2$ (Theorem 3.5). Then $\operatorname{im}T=\operatorname{span}\{e_1,e_2\}$, and $T(a,b,c,d)=(c,d,0,0)$ vanishes exactly when $c=d=0$, so $\ker T=\operatorname{span}\{e_1,e_2\}$ as well.
(c) True $T^2=0$ means $T(Tv)=0$ for all $v$: $\operatorname{im}T\subseteq\ker T$. Hence $\operatorname{rank}T\le\operatorname{nullity}T=n-\operatorname{rank}T$, so $\operatorname{rank}T\le n/2$. Example (b) shows the bound is attained.
(d) False By Theorem 3.7(2) an injective map needs $3\le2$. Concretely, nullity $=3-\operatorname{rank}\ge3-2=1$.
(e) True if $\dim V\lt\infty$ Theorem 3.7(3). It is false in infinite dimension: on the space of real sequences, the left shift $S(a_1,a_2,\dots)=(a_2,a_3,\dots)$ and the right shift $T(a_1,a_2,\dots)=(0,a_1,a_2,\dots)$ satisfy $ST=I$ but $TS(a_1,a_2,\dots)=(0,a_2,a_3,\dots)\ne(a_1,a_2,\dots)$ in general.

Matrices of Linear Maps and Change of Basis

📘 Definition 3.6 — The matrix of a linear map
Let $\mathcal{B}=(b_1,\dots,b_n)$ be an ordered basis of $V$, $\mathcal{C}=(c_1,\dots,c_m)$ an ordered basis of $W$, and $T\in\mathcal{L}(V,W)$. Write $Tb_j=\sum_{i=1}^ma_{ij}c_i$. The $m\times n$ matrix $[T]_{\mathcal{B}}^{\mathcal{C}}=(a_{ij})$ is the matrix of $T$ relative to $\mathcal{B}$ and $\mathcal{C}$: its $j$-th column is $[Tb_j]_{\mathcal{C}}$. For $T\in\mathcal{L}(V)$ we write $[T]_{\mathcal{B}}=[T]_{\mathcal{B}}^{\mathcal{B}}$.
📐 Theorem 3.8 — Matrices represent maps; products represent compositions
With the notation of Definition 3.6:
  1. $[Tv]_{\mathcal{C}}=[T]_{\mathcal{B}}^{\mathcal{C}}\,[v]_{\mathcal{B}}$ for every $v\in V$;
  2. 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}}$;
  3. $T\mapsto[T]_{\mathcal{B}}^{\mathcal{C}}$ is an isomorphism $\mathcal{L}(V,W)\to M_{m\times n}(\mathbb{F})$;
  4. $\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}$. ∎

📘 Definition 3.7 — Transition matrix; similar and equivalent matrices
If $\mathcal{B}$ and $\mathcal{B}'=(b'_1,\dots,b'_n)$ are ordered bases of $V$, the transition matrix from $\mathcal{B}'$ to $\mathcal{B}$ is $P=[I]_{\mathcal{B}'}^{\mathcal{B}}$: its $j$-th column is $[b'_j]_{\mathcal{B}}$ (the new vectors written in the old basis). It is invertible and $[v]_{\mathcal{B}}=P\,[v]_{\mathcal{B}'}$. Matrices $A,B\in M_n(\mathbb{F})$ are similar if $B=P^{-1}AP$ for some invertible $P$; matrices $A,B\in M_{m\times n}(\mathbb{F})$ are equivalent if $B=QAP$ for some invertible $Q\in M_m$, $P\in M_n$.
📐 Theorem 3.9 — The change-of-basis formula
If $T\in\mathcal{L}(V)$ and $P$ is the transition matrix from $\mathcal{B}'$ to $\mathcal{B}$, then $$[T]_{\mathcal{B}'}=P^{-1}\,[T]_{\mathcal{B}}\,P .$$ More generally, for $T\in\mathcal{L}(V,W)$, with transition matrices $P$ (from $\mathcal{B}'$ to $\mathcal{B}$ in $V$) and $Q$ (from $\mathcal{C}'$ to $\mathcal{C}$ in $W$): $[T]_{\mathcal{B}'}^{\mathcal{C}'}=Q^{-1}[T]_{\mathcal{B}}^{\mathcal{C}}P$. So two matrices represent the same operator in different bases if and only if they are similar.

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}$). ∎

📐 Theorem 3.10 — Similarity invariants; equivalence is decided by rank
  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)$.
  2. 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.
The converse of (1) is false: $I_2$ and $\begin{pmatrix}1&1\\0&1\end{pmatrix}$ share rank, trace, determinant and characteristic polynomial, but the only matrix similar to $I$ is $P^{-1}IP=I$.

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. ∎

✏️ Example 5 — The shift operator in two bases
Let $T:P_2(\mathbb{R})\to P_2(\mathbb{R})$, $T(p)(x)=p(x+1)$. (a) Find $A=[T]_{\mathcal{B}}$ for $\mathcal{B}=(1,x,x^2)$. (b) Find $[T]_{\mathcal{B}'}$ for the "binomial" basis $\mathcal{B}'=\left(1,\ x,\ \tfrac12x(x-1)\right)$, directly and by Theorem 3.9. (c) Find the rank of $T-I$ and show $(T-I)^3=0$.
(a) $T(1)=1$, $T(x)=1+x$, $T(x^2)=1+2x+x^2$. These coordinate vectors are the columns: $$A=\begin{pmatrix}1&1&1\\0&1&2\\0&0&1\end{pmatrix}.$$
(b) Directly Put $\beta_0=1$, $\beta_1=x$, $\beta_2=\tfrac12x(x-1)$. Then $T\beta_0=\beta_0$, $T\beta_1=x+1=\beta_0+\beta_1$, and $T\beta_2=\tfrac12(x+1)x=\tfrac12x(x-1)+x=\beta_1+\beta_2$ (Pascal's rule). So $$[T]_{\mathcal{B}'}=\begin{pmatrix}1&1&0\\0&1&1\\0&0&1\end{pmatrix}.$$
(b) By the formula $\beta_2=-\tfrac12x+\tfrac12x^2$, so the transition matrix has columns $(1,0,0)$, $(0,1,0)$, $(0,-\tfrac12,\tfrac12)$: $$P=\begin{pmatrix}1&0&0\\0&1&-\tfrac12\\0&0&\tfrac12\end{pmatrix},\quad P^{-1}=\begin{pmatrix}1&0&0\\0&1&1\\0&0&2\end{pmatrix}.$$ Multiplying out, $P^{-1}AP$ is the matrix found directly. ✓ (Both have trace $3$ and determinant $1$, as Theorem 3.10 requires.)
(c) $[T-I]_{\mathcal{B}'}$ has $1$'s just above the diagonal and zeros elsewhere: rank $2$; its square has a single $1$ in the corner, and its cube is $0$. In terms of polynomials, $(T-I)p(x)=p(x+1)-p(x)$ is the forward difference, which lowers the degree by one; three differences kill every quadratic. Section 3.2 will call $[T]_{\mathcal{B}'}$ a Jordan block: $\mathcal{B}'$ is the basis that makes $T$ simplest.

Rank and Systems of Linear Equations

📘 Definition 3.8 — Row operations, echelon forms, the fundamental subspaces

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)$.

📐 Theorem 3.11 — Row rank equals column rank
  1. 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.)
  2. Every matrix can be brought to RREF by row operations (Gauss–Jordan elimination), and the RREF is unique.
  3. 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}.$$
  4. $\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. ∎

📐 Theorem 3.12 — Rank rules
Let $A\in M_{m\times n}(\mathbb{F})$ and $B\in M_{n\times p}(\mathbb{F})$.
  1. $\operatorname{rank}(AB)\le\min(\operatorname{rank}A,\operatorname{rank}B)$; and $\operatorname{rank}(QAP)=\operatorname{rank}A$ for invertible $Q,P$.
  2. $\operatorname{rank}(A+C)\le\operatorname{rank}A+\operatorname{rank}C$ for $C\in M_{m\times n}$.
  3. 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$.
  4. 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}$).
  5. $\operatorname{rank}A\le\min(m,n)$; a square matrix is invertible iff it has full rank.
  6. $\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. ∎

📐 Theorem 3.13 — The Rouché–Capelli theorem
Let $A\in M_{m\times n}(\mathbb{F})$, $b\in\mathbb{F}^m$, and $r=\operatorname{rank}A$. Write $[A\,|\,b]$ for the augmented matrix.
  1. $Ax=b$ has a solution if and only if $\operatorname{rank}A=\operatorname{rank}[A\,|\,b]$.
  2. 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$.
  3. 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$).
  4. 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). ∎

📐 Theorem 3.14 — The invertible matrix theorem; Cramer's rule

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$. ∎

🧭 A system with parameters, in GATE time
  1. Row reduce the augmented matrix, keeping the parameters in the last rows; never divide by an expression that might be $0$.
  2. Read off the last nonzero row of the coefficient part, typically $(\text{expression in }\lambda)\,z=(\text{expression in }\mu)$.
  3. 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.
  4. 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.
✏️ Example 6 — A system with two parameters
For which real $\lambda,\mu$ does the system $$\begin{aligned}x+2y-z&=3\\2x+5y+z&=8\\x+3y+\lambda z&=\mu\end{aligned}$$ have no solution, exactly one solution, infinitely many solutions? Solve it in the last case.
Eliminate $R_2-2R_1$ gives $y+3z=2$; $R_3-R_1$ gives $y+(\lambda+1)z=\mu-3$; subtracting these, $(\lambda-2)z=\mu-5$. The echelon form of $[A\,|\,b]$ is $$\left(\begin{array}{ccc|c}1&2&-1&3\\0&1&3&2\\0&0&\lambda-2&\mu-5\end{array}\right).$$
Cases $\lambda\ne2$: rank $3$, a unique solution, with $z=\dfrac{\mu-5}{\lambda-2}$, $y=2-3z$, $x=3-2y+z$. $\lambda=2$, $\mu\ne5$: $\operatorname{rank}A=2\lt\operatorname{rank}[A\,|\,b]=3$, no solution. $\lambda=2$, $\mu=5$: both ranks $2$, a one-parameter family.
Solve With $\lambda=2,\mu=5$ and $z=s$: $y=2-3s$, $x=3-2(2-3s)+s=-1+7s$. Solutions: $(x,y,z)=(-1,2,0)+s(7,-3,1)$, $s\in\mathbb{R}$ — a line, the translate of the one-dimensional null space $\operatorname{span}\{(7,-3,1)\}$ by a particular solution.
Check $(7,-3,1)$: $7-6-1=0$, $14-15+1=0$, $7-9+2=0$ ✓. $(-1,2,0)$: $-1+4=3$, $-2+10=8$, $-1+6=5$ ✓. Interactive 2 below runs this elimination for any $(\lambda,\mu)$.
✏️ Example 7 — Rank arguments without computation
Let $A$ be a real $4\times3$ matrix of rank $3$ and $B$ any real $3\times4$ matrix. Decide: (a) $AB$ is invertible; (b) $A^{\mathsf T}A$ is invertible; (c) for every $b\in\mathbb{R}^4$, $Ax=b$ has at most one solution; (d) there is a $3\times4$ matrix $L$ with $LA=I_3$; (e) there is a $3\times4$ matrix $R$ with $AR=I_4$.
(a) False $AB$ is $4\times4$ with $\operatorname{rank}(AB)\le\operatorname{rank}A=3\lt4$ (Theorem 3.12(1)).
(b) True $A^{\mathsf T}A$ is $3\times3$ of rank $\operatorname{rank}A=3$ (Theorem 3.12(4)).
(c) True $\dim N(A)=3-3=0$, so by Theorem 3.13(2) there is at most one solution (but for some $b$ there is none, because $C(A)$ is a $3$-dimensional subspace of $\mathbb{R}^4$).
(d) True $L=(A^{\mathsf T}A)^{-1}A^{\mathsf T}$ works, by (b). This $L$ is the matrix of the least-squares solution.
(e) False $\operatorname{rank}(AR)\le3$, while $\operatorname{rank}I_4=4$.
⚠️ Counterexamples and pitfalls
  1. 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)).
  2. 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\}$.
  3. 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).
  4. 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$.
  5. 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.
  6. 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.
  7. $\ker T=\operatorname{im}T$ forces $\dim V$ even (Example 4(a)).
  8. 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.
  9. 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.
  10. $\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$.
  11. $\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$.
  12. 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.
  13. $\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$.
📚 Go deeper — full proofs in the CSIR NET course

Two Labs

Interactive 1 — A Linear Map of the Plane: Image, Kernel and Rank

The grey grid is the image of the square grid under $A_t=(1-t)I+tA$: as $t$ runs from $0$ to $1$ the identity turns into $A$. The red and blue arrows are $A_te_1$ and $A_te_2$ — the columns — and the purple parallelogram is the image of the unit square, of area $|\det A_t|$. When $A$ has rank $1$, watch the plane collapse at $t=1$: the image is the green line and the amber kernel line is crushed to $0$. Rank + nullity is always $2$.

t—
det Aₜ—
rank—
nullity—
Interactive 2 — Elimination and the Parameter Plane

Left: the augmented matrix of Example 6 is reduced step by step (the row being changed is highlighted). Right: the $(\lambda,\mu)$-plane. Every point off the line $\lambda=2$ gives a unique solution (green); the line $\lambda=2$ gives no solution (red) except at the single point $(2,5)$, where there are infinitely many (blue). Move the sliders, or press Play to run the elimination for several parameter values.

(λ, μ)—
rank A—
rank [A|b]—
solutions—

Exercises

I
Spaces, subspaces, bases and dimension.
  • 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 It is the null space of a $2\times3$ matrix, so a subspace. $y=2x$ and $z=x+2y=5x$: $W=\operatorname{span}\{(1,2,5)\}$, dimension $1$.
2 Singular matrices: no, $\operatorname{diag}(1,0)+\operatorname{diag}(0,1)=I$. $\{a_{11}=a_{22}\}$: yes, the kernel of the linear functional $A\mapsto a_{11}-a_{22}$; dimension $3$.
3 Skew-symmetric: the entries above the diagonal are free and determine the rest, so $\tfrac{n(n-1)}2$. Upper triangular with trace $0$: $\tfrac{n(n+1)}2-1$ (one nonzero linear condition).
4 $p=a+bx+cx^2+dx^3$. $p(2)-p(0)=2b+4c+8d=0$ and $p'(1)=b+2c+3d=0$. Halving the first and subtracting gives $d=0$, then $b=-2c$. So $p=a+c(x^2-2x)$: basis $\{1,\ x^2-2x\}$, dimension $2$.
5 The matrix with these columns has determinant $-2\ne0$, so they form a basis. $a(1,1,0)+b(1,0,1)+c(0,1,1)=(a+b,a+c,b+c)=(2,3,5)$; adding, $a+b+c=5$, so $(a,b,c)=(0,2,3)$. Over $\mathbb{F}_2$ the determinant $-2$ is $0$ — indeed the three vectors add up to $0$ there — so it is not a basis of $\mathbb{F}_2^3$.
6 $\dim U=3$, $\dim W=4-2=2$. $U\cap W$: $x_1=x_2=a$, $x_3=x_4=-2a$, so $\operatorname{span}\{(1,1,-2,-2)\}$, dimension $1$. $\dim(U+W)=3+2-1=4$, so $U+W=\mathbb{R}^4$, but the sum is not direct.
7 $\binom53_2=\binom52_2=\dfrac{(32-1)(32-2)}{(4-1)(4-2)}=\dfrac{31\cdot30}6=155$. A $3$-dimensional subspace has $2^3=8$ vectors, so $32-8=24$ lie outside it.
8 If $V=U\cup W$, then $U\cup W$ is a subspace, so by Theorem 3.1(3) one contains the other, say $U\subseteq W$; then $V=W$, which is not proper. In $\mathbb{F}_2^2$ the lines $\operatorname{span}\{(1,0)\}$, $\operatorname{span}\{(0,1)\}$, $\operatorname{span}\{(1,1)\}$ contain all four vectors.
9 Basis $(1,0),(i,0),(0,1),(0,i)$; $\dim_{\mathbb{R}}V=4$. The set $\{(z,\bar z)\}$ is closed under addition and real scalars: a real subspace of dimension $2$ (basis $(1,1),(i,-i)$). It is not complex: $i(1,1)=(i,i)$, but $\bar i=-i\ne i$.
II
Linear maps and rank–nullity.
  • 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 $T=0$ iff $x=y=z$: $\ker T=\operatorname{span}\{(1,1,1)\}$. The coordinates of $Tv$ always add up to $0$, so $\operatorname{im}T\subseteq\{a+b+c=0\}$; by rank–nullity $\operatorname{rank}T=2$, so the image is that whole plane.
2 $\ker D$ = constants (nullity $1$), $\operatorname{im}D=P_{n-1}$ (rank $n$); $1+n=\dim P_n$. $D^{n+1}=0$ but $D^n(x^n)=n!\ne0$: least $k=n+1$.
3 $\ker T$ = skew-symmetric matrices, $\operatorname{im}T$ = symmetric matrices (each symmetric $S$ is $T(\tfrac12S)$, and $A+A^{\mathsf T}$ is symmetric). $\tfrac{n(n-1)}2+\tfrac{n(n+1)}2=n^2$. ✓
4 The trace is a nonzero functional, so its rank is $1$ and its nullity is $n^2-1$.
5 No. $(1,2,1)=(1,1,0)+(0,1,1)$, so linearity would force $T(1,2,1)=(1,0,0)+(0,1,0)=(1,1,0)\ne(1,1,1)$.
6 $\operatorname{rank}T\le4$, so $\operatorname{nullity}T=7-\operatorname{rank}T\ge3$; hence never injective. Not necessarily surjective: the zero map has rank $0$.
7 Apply rank–nullity to $T$ restricted to $\operatorname{im}T$: its image is $\operatorname{im}T^2$ and its kernel is $\ker T\cap\operatorname{im}T$, so $\operatorname{rank}T^2=\operatorname{rank}T-\dim(\ker T\cap\operatorname{im}T)$. Equal ranks force $\ker T\cap\operatorname{im}T=\{0\}$, and then $\dim(\ker T+\operatorname{im}T)=(n-r)+r=n$ by Theorem 3.3.
8 $v=Tv+(v-Tv)$ with $Tv\in\operatorname{im}T$ and $T(v-Tv)=Tv-T^2v=0$. If $v\in\ker T\cap\operatorname{im}T$, $v=Tu$, then $v=Tu=T^2u=Tv=0$. So the sum is direct. Moreover $\operatorname{im}(I-T)=\ker T$ (each $v-Tv$ lies in $\ker T$, and $v\in\ker T$ gives $v=(I-T)v$), so $\operatorname{rank}T+\operatorname{rank}(I-T)=\operatorname{rank}T+\operatorname{nullity}T=n$.
9 $p\mapsto xp$ is injective, but its image misses the constants. $p\mapsto p'$ is surjective (integrate), but kills the constants. Theorem 3.7(3) needs $\dim V=\dim W\lt\infty$; $\mathbb{R}[x]$ is infinite-dimensional.
III
Matrices of linear maps, change of basis, similarity.
  • 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 $D1=0$, $Dx=1$, $Dx^2=2x$, $Dx^3=3x^2$, so the matrix is $\begin{pmatrix}0&1&0&0\\0&0&2&0\\0&0&0&3\end{pmatrix}$, of rank $3$ (nullity $1$: the constants).
2 $T(1,1)=(3,0)=\tfrac32(1,1)+\tfrac32(1,-1)$ and $T(1,-1)=(1,2)=\tfrac32(1,1)-\tfrac12(1,-1)$, so $[T]_{\mathcal{B}}=\begin{pmatrix}\tfrac32&\tfrac32\\\tfrac32&-\tfrac12\end{pmatrix}$. Trace $1$ and determinant $-\tfrac34-\tfrac94=-3$, the same as for $\begin{pmatrix}2&1\\1&-1\end{pmatrix}$. ✓
3 $E_{11},E_{22}$ are fixed and $E_{12}\leftrightarrow E_{21}$ are swapped, so the matrix is the permutation matrix that swaps the 2nd and 3rd coordinates: trace $2$, determinant $-1$. The transpose fixes the $3$-dimensional space of symmetric matrices and negates the $1$-dimensional space of skew ones; in a basis adapted to $M_2=\text{Sym}\oplus\text{Skew}$ its matrix is $\operatorname{diag}(1,1,1,-1)$, with trace $2$ and determinant $-1$.
4 $\operatorname{tr}(AB-BA)=0$ by Theorem 3.10(1), while $\operatorname{tr}I=n\ne0$. (The argument fails over $\mathbb{F}_p$ when $p\mid n$.)
5 First pair: similar. With $P=\begin{pmatrix}1&2\\2&-1\end{pmatrix}$ (columns $(1,2)$ and $(2,-1)$, which $A$ sends to $5(1,2)$ and $0$), $P^{-1}AP=\operatorname{diag}(5,0)$. Second pair: not similar, the traces are $5$ and $0$; but they are equivalent, both having rank $1$.
6 The columns of $P$ are the new vectors in old coordinates: $P=\begin{pmatrix}1&1&1\\0&1&1\\0&0&1\end{pmatrix}$, $P^{-1}=\begin{pmatrix}1&-1&0\\0&1&-1\\0&0&1\end{pmatrix}$, and $[v]_{\mathcal{B}'}=P^{-1}(1,2,3)^{\mathsf T}=(-1,-1,3)^{\mathsf T}$. Check: $-b_1-(b_1+b_2)+3(b_1+b_2+b_3)=b_1+2b_2+3b_3$. ✓
7 Equivalence is decided by rank (Theorem 3.10(2)), which can be $0,1,2,3$: four classes.
8 $P=\begin{pmatrix}0&1\\1&0\end{pmatrix}=P^{-1}$ swaps the basis vectors: $P\begin{pmatrix}1&1\\0&1\end{pmatrix}P=\begin{pmatrix}1&0\\1&1\end{pmatrix}$. (This is the operator of Example 5 written in the reversed basis.)
IV
Rank and linear systems.
  • 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.
1 Each row minus the previous one is $(1,1,1,1)$, so the rows lie in $\operatorname{span}\{(1,2,3,4),(1,1,1,1)\}$, and these two are independent. Rank $2$. (Equivalently $a_{ij}=i+(j-1)$ is a sum of two rank-one matrices.)
2 $\det=(k-1)^2$. For $k\ne1$ the rank is $3$; for $k=1$ every row is $(1,1,1)$ and the rank is $1$. Rank $2$ never occurs.
3 $R_2-2R_1$: $y-z=t-2$; $R_3-4R_1$: $3y-3z=t^2-4$; then $R_3-3R_2$: $0=t^2-3t+2=(t-1)(t-2)$. Consistent iff $t\in\{1,2\}$. $t=1$: $y=s-1$, $z=s$, $x=1-y-z=2-2s$. $t=2$: $y=z=s$, $x=1-2s$. (Each is a line in $\mathbb{R}^3$: rank $2$, one free parameter.)
4 $C(A)$ is a $3$-dimensional subspace of $\mathbb{R}^3$, hence all of $\mathbb{R}^3$, so $\operatorname{rank}[A\,|\,b]=3=\operatorname{rank}A$ for every $b$. The solution set is $x_p+N(A)$ with $\dim N(A)=5-3=2$: a plane (not through $0$ unless $b=0$) in $\mathbb{R}^5$.
5 $\det A=-10$; replacing columns by $b=(1,4,5)$ gives determinants $-12$, $0$, $-14$. So $x=\tfrac{-12}{-10}=\tfrac65$, $y=0$, $z=\tfrac{-14}{-10}=\tfrac75$. Check: $\tfrac{12}5-\tfrac75=1$, $\tfrac65+\tfrac{14}5=4$, $\tfrac{18}5+\tfrac75=5$. ✓
6 As in Theorem 3.12(4): $A^{\mathsf T}Ax=0\Rightarrow\|Ax\|^2=x^{\mathsf T}A^{\mathsf T}Ax=0\Rightarrow Ax=0$, so $N(A^{\mathsf T}A)=N(A)$, and rank–nullity on $n$ columns gives equal ranks. Complex failure: $A=\begin{pmatrix}1\\i\end{pmatrix}$, $A^{\mathsf T}A=(0)$ but $\operatorname{rank}A=1$.
7 $AB=0$ means $C(B)\subseteq N(A)$, so $\operatorname{rank}B\le n-\operatorname{rank}A$ (or use Sylvester). Equality: $A=\operatorname{diag}(1,1,0,0)$, $B=\operatorname{diag}(0,0,1,1)$.
8 At $A$: $x_4+400=x_1$; at $B$: $x_1=x_2+250$; at $C$: $x_2+150=x_3$; at $D$: $x_3=x_4+300$. The coefficient matrix has rank $3$ (the four equations add up to $0=0$, since $550$ vehicles/h enter and $550$ leave), so there is one free parameter: $x_4=s$, $x_1=s+400$, $x_2=s+150$, $x_3=s+300$. Non-negativity only requires $s\ge0$, so the smallest flows are $x_1=400$, $x_2=150$, $x_3=300$, $x_4=0$ vehicles per hour (traffic never needs to use the street $D\to A$; any traffic circling the block adds the same $s$ to all four streets).
🎯 GATE corner GATE MA · MCQGATE MA · MSQGATE MA · NAT

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$.

Idea Split $p=p_{\rm even}+p_{\rm odd}$ with $p_{\rm odd}=a_1x+a_3x^3+a_5x^5$. Each condition $p(c)=p(-c)$ says $p_{\rm odd}(c)=0$, and $p'(0)=0$ says $a_1=0$.
Rank of the conditions $p_{\rm odd}(1)=p_{\rm odd}(2)=p_{\rm odd}(3)=0$ give the system $a_1+a_3+a_5=0$, $a_1+4a_3+16a_5=0$, $a_1+9a_3+81a_5=0$ (after dividing by $c$), a Vandermonde system in $1,4,9$ with only the trivial solution. So the four conditions together say exactly $a_1=a_3=a_5=0$: they have rank $3$, not $4$.
Answer $W$ is the space of even polynomials $a_0+a_2x^2+a_4x^4$: $\dim W=6-3=3$, option (B). (A) is the trap "$6-4$".

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$.

Eliminate $R_2-2R_1$: $y-3z=-3$. $R_3-3R_1$: $y+(a-6)z=b-6$. Subtract: $(a-3)z=b-3$.
Options (C) $a\ne3$ gives a unique solution. (B) $a=3$, $b\ne3$ gives $0=b-3\ne0$: no solution. (A) $a=b=3$: both ranks $2\lt3$, infinitely many. (D) gives $3z=3$, a unique solution.
Answer (A).

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$.

(A) True $AB$ is $5\times5$ with $\operatorname{rank}(AB)\le\operatorname{rank}A\le3\lt5$.
(B) False $BA$ is $3\times3$ and can be invertible: $A=\begin{pmatrix}I_3\\0\end{pmatrix}$, $B=\begin{pmatrix}I_3&0\end{pmatrix}$ give $BA=I_3$.
(C) True $\operatorname{rank}(A^{\mathsf T}A)=\operatorname{rank}A=3$ (Theorem 3.12(4)), and $A^{\mathsf T}A$ is $3\times3$.
(D) True Sylvester with inner dimension $n=3$: $\operatorname{rank}A+\operatorname{rank}B-3\le\operatorname{rank}(AB)=0$.
Answer (A), (C) and (D).

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$.

(A) True The kernel of the linear map $\operatorname{tr}$ (dimension $8$).
(B) False $E_{11}+E_{22}$ and $E_{33}$ are singular, their sum $I$ is not.
(C) True If $A^{\mathsf T}=2A$ then $A=(A^{\mathsf T})^{\mathsf T}=2A^{\mathsf T}=4A$, so $A=0$. The set is $\{0\}$ — the zero subspace, which is a subspace. (Directly: it is the kernel of the linear map $A\mapsto A^{\mathsf T}-2A$.)
(D) True The kernel of the linear map $A\mapsto Av$ (dimension $6$ if $v\ne0$).
Answer (A), (C) and (D).

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 ______.

Idea Theorem 3.4(3): ordered pairs of independent vectors divided by ordered bases of a plane.
Compute $\dfrac{(3^4-1)(3^4-3)}{(3^2-1)(3^2-3)}=\dfrac{80\cdot78}{8\cdot6}=\dfrac{6240}{48}=130$.
Answer $130$ (an integer; accept exactly $130$). Dividing only by the $8$ nonzero vectors of a plane — forgetting that its second basis vector can be chosen in $6$ ways — gives the wrong count $780$.

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 ______.

Idea $(i+j)^2=i^2\cdot1+2\,i\cdot j+1\cdot j^2$, so $A=uw^{\mathsf T}+2vv^{\mathsf T}+wu^{\mathsf T}$ with $u=(i^2)_i$, $v=(i)_i$, $w=(1)_i$. Every column lies in $\operatorname{span}\{u,v,w\}$, so $\operatorname{rank}A\le3$.
Rank exactly 3 The top-left $3\times3$ block $\begin{pmatrix}4&9&16\\9&16&25\\16&25&36\end{pmatrix}$ has determinant $-8\ne0$ (Theorem 3.11(4)).
Answer Nullity $=6-3=3$. Answer: $3$.
🧑‍🏫 For the teacher

Suggested plan — 3 lectures × 60 min.

  1. 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.
  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$.
  3. 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–Teaching NexusResearch-tutored · optional, about 60 minutes

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.

  1. 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.
  2. 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.
  3. 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.
  4. 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.

Instructor note: rows of $H$ (with column $j$ = binary expansion of $j$, most significant bit on top) are $0001111$, $0110011$, $1010101$; columns $1,2,4$ are the identity, so the rank is $3$ and $\dim C=7-3=4$. The weight distribution of $C$ is one word of weight $0$, seven of weight $3$, seven of weight $4$ and one of weight $7$ (minimum distance $3$, so one error is corrected). With this column order the syndrome read as a binary number is exactly the error position — students find this very satisfying. Two errors give the syndrome of a third position, which the decoder "corrects", producing a wrong codeword.

🧪 Self-check quiz

0/5 correct

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?