Chapter 8 · Vector Spaces and Linear Transformations

8.3 Rank, Determinants and Linear Equations

Row reduction computes almost everything about a matrix — its rank, bases of its row, column and null spaces, its determinant and its inverse — and the rank alone decides whether $Ax=b$ has no solution, exactly one, or a whole affine family of them.

A system of $m$ linear equations in $n$ unknowns is the most common computational object in mathematics: it appears when we fit a curve to data, balance a chemical reaction, find the currents in an electrical network, discretise a differential equation or test whether vectors are independent. Two numbers attached to its coefficient matrix answer every structural question about it. The rank tells us whether the system is consistent and how many free parameters its solution set has; the determinant of a square matrix tells us in one number whether the solution is unique, and gives an explicit formula for it (Cramer's rule). Both are computed by the same humble algorithm — Gaussian elimination — and the main work of this section is to prove that what the algorithm produces does not depend on the choices made along the way.

We work over a field $\mathbb{F}$ (usually $\mathbb{R}$ or $\mathbb{C}$, sometimes $\mathbb{F}_q$), with $M_{m\times n}(\mathbb{F})$ the $m\times n$ matrices and $M_n(\mathbb{F})=M_{n\times n}(\mathbb{F})$, as in §8.1. A matrix $A\in M_{m\times n}(\mathbb{F})$ is identified with the linear map $x\mapsto Ax$ from $\mathbb{F}^n$ to $\mathbb{F}^m$, so the rank–nullity theorem of §8.2 applies to it. CSIR NET tests this material in every paper: Part B asks for ranks of patterned matrices, determinants of structured matrices, $\det(\operatorname{adj}A)$, or the parameter values for which a system is consistent; Part C asks which rank inequalities, determinant identities or properties of nilpotent, idempotent and orthogonal matrices are true — and the traps are the counterexamples collected in the ⚠️ box below.

Row Reduction, Echelon Forms and Rank

📘 Definition 8.19 — Elementary row operations and elementary matrices

The three elementary row operations on a matrix are:

Swap$R_i\leftrightarrow R_j$: interchange rows $i\ne j$.
Scale$R_i\to cR_i$: multiply row $i$ by a scalar $c\ne0$.
Replace$R_i\to R_i+cR_j$: add $c$ times row $j$ to row $i$ ($j\ne i$).

An elementary matrix is a matrix obtained from the identity $I_m$ by one elementary row operation. Two matrices are row equivalent, $A\sim B$, if one is obtained from the other by a finite sequence of elementary row operations. Elementary column operations are defined in the same way.

📐 Theorem 8.30 — Row operations are multiplications by invertible matrices

Let $A\in M_{m\times n}(\mathbb{F})$ and let $E$ be the elementary matrix of a row operation $\rho$. Then $\rho(A)=EA$. Every elementary matrix is invertible, and its inverse is the elementary matrix of the reverse operation ($R_i\leftrightarrow R_j$; $R_i\to c^{-1}R_i$; $R_i\to R_i-cR_j$). Consequently $A\sim B$ if and only if $B=PA$ for some $P$ that is a product of elementary matrices, and row equivalence is an equivalence relation. Elementary column operations correspond to multiplication on the right by elementary matrices.

Proof. Row $i$ of a product $EA$ is $\sum_k e_{ik}\,(\text{row }k\text{ of }A)$, so $EA$ is determined by what $E$ does to the rows of $I_m$. Each of the three operations acts on rows by such a linear recipe that does not depend on $A$; applying it to $I_m$ produces $E=\rho(I_m)$, and then $\rho(A)=\rho(I_m)A=EA$. The reverse operation $\rho'$ satisfies $\rho'(\rho(A))=A$ for every $A$, so with $E'=\rho'(I_m)$ we get $E'E=E'EI_m=\rho'(\rho(I_m))=I_m$ and likewise $EE'=I_m$. Products of invertible matrices are invertible, which gives the statement about $\sim$: reflexive ($P=I$), symmetric ($P^{-1}$ is again a product of elementary matrices) and transitive (multiply). For columns, $(AE^{T})^{T}=EA^{T}$ shows that right multiplication by $E^T$ (again elementary) performs the column version of $\rho$. ∎

📘 Definition 8.20 — Row echelon form and reduced row echelon form

The leading entry of a nonzero row is its first nonzero entry. A matrix is in row echelon form if (i) all zero rows are at the bottom, and (ii) the leading entry of each nonzero row lies strictly to the right of the leading entry of the row above it. It is in reduced row echelon form (RREF) if moreover (iii) every leading entry equals $1$ and (iv) each leading $1$ is the only nonzero entry in its column. The leading entries are the pivots; their columns are the pivot columns, the other columns are free columns.

📐 Theorem 8.31 — Gauss–Jordan elimination: existence and uniqueness of the RREF
Every $A\in M_{m\times n}(\mathbb{F})$ is row equivalent to exactly one matrix $R$ in reduced row echelon form, denoted $\operatorname{rref}(A)$. Thus $A=PR$ with $P$ invertible.

Proof. Existence (the algorithm). Find the first column containing a nonzero entry; swap a row with a nonzero entry in that column to the top, scale it so that the entry is $1$, and use replacements to make every other entry of that column $0$. Now repeat the procedure on the rows below the first, looking only at columns to the right of the pivot just created, but continue to clear entries above each new pivot as well. Each round fixes one more pivot and never disturbs the earlier pivot columns (a replacement $R_i\to R_i+cR_k$ with $R_k$ the new pivot row adds $0$ to the earlier pivot columns, because $R_k$ has zeros there). After at most $\min(m,n)$ rounds the matrix satisfies (i)–(iv).

Uniqueness. The key observation: if $B=PA$ with $P$ invertible, then $Ax=0\iff Bx=0$, so a linear relation $\sum_j x_ja_j=0$ among the columns $a_j$ of $A$ holds if and only if the same relation holds among the columns of $B$. Now let $R$ be any RREF row equivalent to $A$, with pivot columns $p_1\lt\cdots\lt p_r$. In $R$, column $p_k$ is the standard vector $e_k$, and every column $j$ has zeros in rows $r+1,\dots,m$. Hence, in $R$ and therefore in $A$: (a) column $j$ is a pivot column if and only if it is not a linear combination of the columns before it (a pivot column $e_k$ is not a combination of columns with zeros in row $k$ and beyond; a free column $j$ with $p_k\lt j\lt p_{k+1}$ has zeros below row $k$, so it is a combination of $e_1,\dots,e_k$, which are earlier pivot columns); (b) a free column $j$ of $R$ equals $\sum_k r_{kj}e_k=\sum_k r_{kj}\,(\text{column }p_k)$, so in $A$ we have $a_j=\sum_k r_{kj}a_{p_k}$, and these coefficients are unique because the columns $a_{p_1},\dots,a_{p_r}$ are independent (they are independent in $R$). So the pivot positions of $R$ and all entries of its free columns are determined by $A$ alone: any two RREFs of $A$ coincide. ∎

📘 Definition 8.21 — The fundamental subspaces and the rank

For $A\in M_{m\times n}(\mathbb{F})$ with columns $a_1,\dots,a_n$:

  • the column space $C(A)=\operatorname{span}\{a_1,\dots,a_n\}$, which equals $\{Ax:x\in\mathbb{F}^n\}\subseteq\mathbb{F}^m$ (the image of $x\mapsto Ax$);
  • the row space $C(A^T)\subseteq\mathbb{F}^n$, spanned by the rows;
  • the null space $N(A)=\{x\in\mathbb{F}^n:Ax=0\}$ (the kernel of $x\mapsto Ax$).

The column rank is $\dim C(A)$, the row rank is $\dim C(A^T)$, and the nullity is $\dim N(A)$.

📐 Theorem 8.32 — Row rank equals column rank

Let $A\in M_{m\times n}(\mathbb{F})$ and let $R=\operatorname{rref}(A)$ have $r$ pivots. Then:

  1. the nonzero rows of $R$ form a basis of the row space of $A$;
  2. the pivot columns of $A$ (not of $R$) form a basis of $C(A)$;
  3. row rank $=$ column rank $=r$. This common value is the rank of $A$, written $\operatorname{rank}A$; in particular $\operatorname{rank}A=\operatorname{rank}A^T\le\min(m,n)$;
  4. (rank–nullity for matrices) $\operatorname{rank}A+\dim N(A)=n$; a basis of $N(A)$ is obtained by giving one free variable the value $1$, the others $0$, and solving for the pivot variables.

If $A$ has entries in a subfield $\mathbb{K}\subseteq\mathbb{F}$ (for example $\mathbb{Q}\subseteq\mathbb{R}\subseteq\mathbb{C}$), its rank is the same whether computed over $\mathbb{K}$ or over $\mathbb{F}$.

Proof. (1) If $B=EA$ with $E$ elementary, every row of $B$ is a combination of rows of $A$, so $C(B^T)\subseteq C(A^T)$; as $A=E^{-1}B$, equality holds. So $A$ and $R$ have the same row space. The nonzero rows of $R$ span it, and they are independent: in a relation $\sum_kc_k(\text{row }k)=0$, look at the pivot column $p_k$, where only row $k$ has a nonzero entry (the leading $1$); this forces $c_k=0$.

(2) By the key observation in the proof of Theorem 8.31, a set of columns of $A$ is independent if and only if the same set of columns of $R$ is, and a column of $A$ is a combination of certain other columns if and only if the same holds in $R$. In $R$ the pivot columns $e_1,\dots,e_r$ are independent and span $C(R)$ (all columns of $R$ vanish below row $r$). Transferring both facts to $A$, the pivot columns of $A$ are independent and every column of $A$ is a combination of them.

(3) Both dimensions equal the number of pivots $r$. Since the row rank of $A$ is the column rank of $A^T$, $\operatorname{rank}A=\operatorname{rank}A^T$. (4) $N(A)=N(R)$, and $Rx=0$ says $x_{p_k}=-\sum_{j\text{ free}}r_{kj}x_j$ for $k=1,\dots,r$: the free variables can be chosen arbitrarily and determine $x$. The $n-r$ vectors described are therefore a basis of $N(R)$ (each has a $1$ in its own free position and $0$ in the other free positions, which proves independence). Finally, Gauss–Jordan elimination on a matrix with entries in $\mathbb{K}$ uses only field operations, so $\operatorname{rref}(A)$ and its number of pivots are the same over $\mathbb{K}$ and over $\mathbb{F}$. ∎

📐 Theorem 8.33 — Rank normal form and rank factorisation

Let $A\in M_{m\times n}(\mathbb{F})$ have rank $r$. Then:

  1. there are invertible $P\in M_m(\mathbb{F})$ and $Q\in M_n(\mathbb{F})$ with $PAQ=\begin{pmatrix}I_r&0\\0&0\end{pmatrix}$; hence two $m\times n$ matrices are equivalent ($B=PAQ$ with $P,Q$ invertible) if and only if they have the same rank;
  2. $A=BC$ with $B\in M_{m\times r}$, $C\in M_{r\times n}$, both of rank $r$ (a rank factorisation);
  3. $\operatorname{rank}A=1$ if and only if $A=uv^T$ for nonzero column vectors $u\in\mathbb{F}^m$, $v\in\mathbb{F}^n$.

Part (1) is the matrix form of the rank normal form proved in §8.2 by choosing adapted bases; here we derive it by elimination, which also shows how to compute $P$ and $Q$.

Proof. (1) Row-reduce: $P_1A=R$. Column swaps bring the pivot columns $e_1,\dots,e_r$ of $R$ to the front, and column replacements subtract multiples of these columns from the free columns until they vanish; these column operations are $R\mapsto RQ$ with $Q$ invertible (Theorem 8.30), and they produce $N_r=\begin{pmatrix}I_r&0\\0&0\end{pmatrix}$. Multiplying by invertible matrices does not change the rank (it does not change the row space when we multiply on the left, and transposes reduce the right case to the left case), so equivalent matrices have equal ranks; conversely two matrices of rank $r$ are both equivalent to $N_r$, hence to each other. (2) $N_r=\begin{pmatrix}I_r\\0\end{pmatrix}\begin{pmatrix}I_r&0\end{pmatrix}$, so $A=P^{-1}N_rQ^{-1}=BC$ with $B=P^{-1}\begin{pmatrix}I_r\\0\end{pmatrix}$ (its columns are $r$ columns of an invertible matrix, hence independent) and $C=\begin{pmatrix}I_r&0\end{pmatrix}Q^{-1}$ (its rows are independent). (3) is (2) with $r=1$; conversely $uv^T$ has every column a multiple of $u\ne0$ and some column nonzero (since $v\ne0$). ∎

✏️ Example 1 — Everything from one RREF
Let $$A=\begin{pmatrix}1&2&0&1&0\\2&4&1&4&0\\1&2&1&3&1\\3&6&1&5&2\end{pmatrix}.$$ Find $\operatorname{rref}(A)$, the rank, and bases of the row space, the column space and the null space. Express each free column of $A$ in terms of the pivot columns.
Eliminate column 1 $R_2\to R_2-2R_1$, $R_3\to R_3-R_1$, $R_4\to R_4-3R_1$ give rows $(0,0,1,2,0)$, $(0,0,1,2,1)$, $(0,0,1,2,2)$. Column 2 has no pivot below row 1 (all zeros), so it is free.
Columns 3 and 5 The pivot of column 3 is in row 2: $R_3\to R_3-R_2$, $R_4\to R_4-R_2$ give $(0,0,0,0,1)$ and $(0,0,0,0,2)$. Column 4 has no pivot below row 2. The pivot of column 5 is in row 3: $R_4\to R_4-2R_3$ gives a zero row. Clearing above the pivots is already done (row 1 has $0$ in columns 3 and 5, row 2 has $0$ in column 5). $$\operatorname{rref}(A)=\begin{pmatrix}1&2&0&1&0\\0&0&1&2&0\\0&0&0&0&1\\0&0&0&0&0\end{pmatrix}.$$
Bases Three pivots (columns 1, 3, 5), so $\operatorname{rank}A=3$. Row space: $(1,2,0,1,0),(0,0,1,2,0),(0,0,0,0,1)$. Column space: columns $1,3,5$ of $A$, i.e. $(1,2,1,3)^T,(0,1,1,1)^T,(0,0,1,2)^T$ — not $e_1,e_2,e_3$, which are not even in $C(A)$ ($e_1=(1,0,0,0)^T$ would need coefficient $1$ on $a_1$, then rows 2 and 3 force $-2$ on $a_3$ and $1$ on $a_5$, and row 4 gives $3-2+2=3\ne0$). Null space (free variables $x_2=s$, $x_4=t$; $x_1=-2s-t$, $x_3=-2t$, $x_5=0$): basis $(-2,1,0,0,0)^T$, $(-1,0,-2,1,0)^T$; nullity $2=5-3$.
Column relations Read off the free columns of the RREF: $a_2=2a_1$ and $a_4=a_1+2a_3$. Check: $a_1+2a_3=(1,2,1,3)^T+2(0,1,1,1)^T=(1,4,3,5)^T=a_4$. ✓
🧭 Problem-solving strategy — computing a rank
  1. Row-reduce to any echelon form (no need to reach the RREF): the rank is the number of nonzero rows. Column operations are allowed too — they also preserve the rank.
  2. Look for structure first. If every entry has the form $a_{ij}=\sum_{k=1}^{s}f_k(i)g_k(j)$, then $A$ is a sum of $s$ rank-one matrices and $\operatorname{rank}A\le s$ (e.g. $a_{ij}=i+j$, $\sin(i+j)$, $(i+j)^2$). Then find $s$ independent rows or columns, or a nonzero $s\times s$ minor (Theorem 8.41), to get equality.
  3. Parameters. For a square matrix depending on $t$, factor $\det A(t)$; the rank is $n$ off the roots, and at each root substitute and row-reduce.
  4. Bounds without computation: $\operatorname{rank}(AB)\le\min(\operatorname{rank}A,\operatorname{rank}B)$, Sylvester's inequality, $\operatorname{rank}(A+B)\le\operatorname{rank}A+\operatorname{rank}B$ (next subsection).
✏️ Example 2 — Ranks of patterned matrices
For $n\ge3$ find the rank of the $n\times n$ matrices $A=(i+j)$, $B=\big((i+j)^2\big)$ and $C=\big(\min(i,j)\big)$, $1\le i,j\le n$.
$A$: rank 2 Let $u=(1,2,\dots,n)^T$ and $\mathbf 1=(1,\dots,1)^T$. Then $a_{ij}=i\cdot1+1\cdot j$, i.e. $A=u\mathbf 1^T+\mathbf 1u^T$, so every column of $A$ lies in $\operatorname{span}\{u,\mathbf 1\}$ and $\operatorname{rank}A\le2$. The first two columns $u+\mathbf 1$ and $u+2\cdot\mathbf 1$ are independent (their difference is $\mathbf 1$, and $u+\mathbf 1$ is not a multiple of $\mathbf 1$), so $\operatorname{rank}A=2$.
$B$: rank 3 $(i+j)^2=i^2\cdot1+2\,i\cdot j+1\cdot j^2$, so every column lies in $\operatorname{span}\{u^{(2)},u,\mathbf 1\}$ where $u^{(2)}=(i^2)_i$: $\operatorname{rank}B\le3$. The top-left $3\times3$ minor is $\det\begin{pmatrix}4&9&16\\9&16&25\\16&25&36\end{pmatrix}=-8\ne0$, so $\operatorname{rank}B=3$ (Theorem 8.41).
$C$: rank $n$ Row $i$ of $C$ is $(1,2,\dots,i,i,\dots,i)$. Perform $R_i\to R_i-R_{i-1}$ for $i=n,n-1,\dots,2$ (in that order, so that each step uses an unchanged row): row $i$ becomes $(0,\dots,0,1,1,\dots,1)$ with the first $1$ in place $i$. The result is upper triangular with $1$s on the diagonal, so $\det C=1$ and $\operatorname{rank}C=n$.
Lesson "Separable" entries $\sum_{k\le s}f_k(i)g_k(j)$ bound the rank by $s$ no matter how large $n$ is; $\min(i,j)$ is not separable in this sense and the matrix is invertible.
Interactive 1 — Gauss–Jordan Elimination, One Operation at a Time

Each step is a single elementary row operation: the green cell is the current pivot, the blue row is the one being changed and the amber row is the one being used. Watch the pivots appear, the rank count up and the determinant factor change only at swaps (sign) and scalings. Try the inverse mode ($[A\mid I]\to[I\mid A^{-1}]$), and in the last two modes move the slider to the parameter value where the rank drops or the system becomes inconsistent.

2
step—
operation—
pivots so far (rank)—
det A = c · det(current)—

Rank Inequalities: Sylvester and Frobenius

CSIR problems rarely ask for a rank that can be computed by elimination; they give a few ranks and ask what the others can be. The following rules, all consequences of the dimension formula of §8.1 and the rank–nullity theorem, answer such questions.

📐 Theorem 8.34 — Basic rank rules

Let $A\in M_{m\times n}(\mathbb{F})$ and let $B$ be of the size required in each statement.

  1. $\operatorname{rank}(AB)\le\min(\operatorname{rank}A,\operatorname{rank}B)$ for $B\in M_{n\times p}(\mathbb{F})$.
  2. $\operatorname{rank}(PAQ)=\operatorname{rank}A$ for invertible $P\in M_m(\mathbb{F})$, $Q\in M_n(\mathbb{F})$.
  3. $\operatorname{rank}(A+B)\le\operatorname{rank}A+\operatorname{rank}B$ and $|\operatorname{rank}A-\operatorname{rank}B|\le\operatorname{rank}(A-B)$ for $B\in M_{m\times n}(\mathbb{F})$.
  4. For $\mathbb{F}=\mathbb{R}$: $N(A^TA)=N(A)$ and $\operatorname{rank}(A^TA)=\operatorname{rank}(AA^T)=\operatorname{rank}A$. For $\mathbb{F}=\mathbb{C}$ the same holds with the conjugate transpose $A^*=\overline{A}^{\,T}$ in place of $A^T$.

Proof. (1) $ABx=A(Bx)$, so $C(AB)\subseteq C(A)$ and $\operatorname{rank}(AB)\le\operatorname{rank}A$. Also $\operatorname{rank}(AB)=\operatorname{rank}(B^TA^T)$, which is $\le\operatorname{rank}B^T=\operatorname{rank}B$ by what was just shown and Theorem 8.32(3). (2) By (1), $\operatorname{rank}(PAQ)\le\operatorname{rank}A$, and $\operatorname{rank}A=\operatorname{rank}\big(P^{-1}(PAQ)Q^{-1}\big)\le\operatorname{rank}(PAQ)$. (3) $(A+B)x=Ax+Bx$, so $C(A+B)\subseteq C(A)+C(B)$, whose dimension is at most $\dim C(A)+\dim C(B)$ by the dimension formula. Applying this to $A=(A-B)+B$ gives $\operatorname{rank}A-\operatorname{rank}B\le\operatorname{rank}(A-B)$, and by symmetry $\operatorname{rank}B-\operatorname{rank}A\le\operatorname{rank}(B-A)=\operatorname{rank}(A-B)$. (4) If $Ax=0$ then $A^TAx=0$. Conversely, if $A^TAx=0$ then $0=x^TA^TAx=(Ax)^T(Ax)=\sum_i(Ax)_i^2$, a sum of real squares, so $Ax=0$. Equal null spaces give equal ranks by rank–nullity (both matrices have $n$ columns). Applying this to $A^T$ gives $\operatorname{rank}(AA^T)=\operatorname{rank}A^T=\operatorname{rank}A$. Over $\mathbb{C}$ the same argument works with $x^*A^*Ax=\sum_i|(Ax)_i|^2$. ∎

Part (4) uses positivity of sums of squares, which is special to $\mathbb{R}$ (and to $A^*A$ over $\mathbb{C}$). It fails for $A^TA$ over $\mathbb{C}$ and over finite fields: see Example 3(e).

The next lemma is the engine behind every lower bound for a rank. If $A\in M_{m\times n}(\mathbb{F})$ and $U\subseteq\mathbb{F}^n$ is a subspace, then applying rank–nullity to the restriction of $x\mapsto Ax$ to $U$ gives

$$\dim A(U)=\dim U-\dim\big(U\cap N(A)\big).\qquad(\ast)$$
📐 Theorem 8.35 — Frobenius' inequality and Sylvester's rank inequality

(a) Frobenius: for $A\in M_{m\times n}$, $B\in M_{n\times p}$, $C\in M_{p\times q}$ over any field,

$$\operatorname{rank}(AB)+\operatorname{rank}(BC)\le\operatorname{rank}B+\operatorname{rank}(ABC).$$

(b) Sylvester: for $A\in M_{m\times n}$ and $C\in M_{n\times q}$,

$$\operatorname{rank}A+\operatorname{rank}C-n\le\operatorname{rank}(AC)\le\min(\operatorname{rank}A,\operatorname{rank}C).$$

More precisely, $\operatorname{rank}(AC)=\operatorname{rank}C-\dim\big(C(C)\cap N(A)\big)$.

Proof. (a) Let $U=C(B)\subseteq\mathbb{F}^n$ and $U'=C(BC)$; then $U'\subseteq U$ because $BCx=B(Cx)$. Moreover $C(AB)=A(U)$ and $C(ABC)=A(U')$. By $(\ast)$,

$$\operatorname{rank}(AB)=\operatorname{rank}B-\dim(U\cap N(A)),$$ $$\operatorname{rank}(ABC)=\operatorname{rank}(BC)-\dim(U'\cap N(A)).$$

Subtracting,

$$\operatorname{rank}(AB)-\operatorname{rank}(ABC)=\operatorname{rank}B-\operatorname{rank}(BC)-\Delta,$$

where $\Delta=\dim(U\cap N(A))-\dim(U'\cap N(A))$, and $\Delta\ge0$ because $U'\cap N(A)\subseteq U\cap N(A)$. Rearranging gives Frobenius' inequality.

(b) The precise formula is $(\ast)$ with $U=C(C)$. Since $\dim(C(C)\cap N(A))\le\dim N(A)=n-\operatorname{rank}A$, we get $\operatorname{rank}(AC)\ge\operatorname{rank}C-n+\operatorname{rank}A$. (Equivalently, take $B=I_n$ in (a).) The upper bound is Theorem 8.34(1). ∎

📐 Theorem 8.36 — Consequences of the rank inequalities
  1. If $A\in M_{m\times n}$, $B\in M_{n\times p}$ and $AB=0$, then $\operatorname{rank}A+\operatorname{rank}B\le n$.
  2. If $A\in M_n(\mathbb{F})$ and $A^2=0$, then $\operatorname{rank}A\le n/2$.
  3. For $A\in M_n(\mathbb{F})$ the drops $d_k=\operatorname{rank}A^{k}-\operatorname{rank}A^{k+1}$ ($k\ge0$, $A^0=I$) satisfy $d_0\ge d_1\ge d_2\ge\cdots\ge0$. Hence once $\operatorname{rank}A^k=\operatorname{rank}A^{k+1}$, all later powers have the same rank; and if $A^k=0$ for some $k$, then $A^n=0$.

Proof. (1) Sylvester: $\operatorname{rank}A+\operatorname{rank}B-n\le\operatorname{rank}(AB)=0$. (2) is (1) with $B=A$. (3) Frobenius with $(A,B,C)=(A,A^k,A)$ gives $\operatorname{rank}A^{k+1}+\operatorname{rank}A^{k+1}\le\operatorname{rank}A^k+\operatorname{rank}A^{k+2}$, i.e. $d_{k+1}\le d_k$; and $d_k\ge0$ by Theorem 8.34(1). If $d_k=0$ then $d_j=0$ for all $j\ge k$. If some power of $A$ is $0$, the ranks $n=\operatorname{rank}A^0\ge\operatorname{rank}A\ge\cdots$ must reach $0$; as long as they are positive they strictly decrease (a zero drop would freeze them at a positive value forever), so they reach $0$ after at most $n$ steps: $A^n=0$. ∎

✏️ Example 3 — Rank statements: prove or disprove
(a) If $A\in M_5(\mathbb{R})$ and $A^2=0$, then $\operatorname{rank}A\le2$. (b) There are $A,B\in M_3(\mathbb{R})$ of rank $2$ with $AB=0$. (c) $\operatorname{rank}(AB)=\operatorname{rank}(BA)$ for all $A,B\in M_2(\mathbb{R})$. (d) If $A\in M_n(\mathbb{F})$ and $\operatorname{rank}A^2=\operatorname{rank}A$, then $\operatorname{rank}A^k=\operatorname{rank}A$ for all $k\ge1$. (e) $\operatorname{rank}(A^TA)=\operatorname{rank}A$ for every complex matrix $A$.
(a) True Theorem 8.36(2): $\operatorname{rank}A\le5/2$, and the rank is an integer. The bound is attained: $A=E_{13}+E_{24}$ (so $Ae_3=e_1$, $Ae_4=e_2$, other $e_j\mapsto0$) has $A^2=0$ and rank $2$.
(b) False $AB=0$ forces $\operatorname{rank}A+\operatorname{rank}B\le3$ (Theorem 8.36(1)), but $2+2=4$. Geometrically: $C(B)\subseteq N(A)$, and $N(A)$ is a line when $\operatorname{rank}A=2$.
(c) False $A=\begin{pmatrix}0&1\\0&0\end{pmatrix}$, $B=\begin{pmatrix}1&0\\0&0\end{pmatrix}$: $AB=0$ but $BA=\begin{pmatrix}0&1\\0&0\end{pmatrix}$ has rank $1$. (It is true when $A$ or $B$ is invertible: $BA=A^{-1}(AB)A$ and Theorem 8.34(2).)
(d) True The drop $d_1=\operatorname{rank}A-\operatorname{rank}A^2=0$, so every later drop is $0$ (Theorem 8.36(3)).
(e) False $A=\begin{pmatrix}1\\ i\end{pmatrix}$ has rank $1$ but $A^TA=1+i^2=0$. The correct complex statement uses $A^*A=1+|i|^2=2$. Over $\mathbb{F}_2$, $A=\begin{pmatrix}1\\1\end{pmatrix}$ gives $A^TA=2=0$ as well.

Determinants: Axioms, Expansion and the Adjugate

For a $2\times2$ matrix, $ad-bc$ is the signed area of the parallelogram spanned by the columns, and it vanishes exactly when the columns are dependent. The determinant of an $n\times n$ matrix is the unique extension of this signed volume that is linear in each row and vanishes on repeated rows. We write $S_n$ for the group of permutations of $\{1,\dots,n\}$ and $\operatorname{sgn}\sigma=(-1)^{N(\sigma)}$, where $N(\sigma)$ is the number of inversions (pairs $i\lt j$ with $\sigma(i)\gt\sigma(j)$). We use the standard facts that $\operatorname{sgn}(\sigma\tau)=\operatorname{sgn}\sigma\,\operatorname{sgn}\tau$, that a transposition has sign $-1$, and hence that $\operatorname{sgn}\sigma^{-1}=\operatorname{sgn}\sigma$ (permutation groups are studied in Unit 2).

📘 Definition 8.22 — The determinant (Leibniz formula)
For $A=(a_{ij})\in M_n(\mathbb{F})$, $$\det A=\sum_{\sigma\in S_n}\operatorname{sgn}(\sigma)\,a_{1\sigma(1)}a_{2\sigma(2)}\cdots a_{n\sigma(n)}.$$ Each of the $n!$ terms takes exactly one entry from each row and each column. For $n=2$: $\det A=a_{11}a_{22}-a_{12}a_{21}$; for $n=3$ the six terms are the familiar "diagonals" of Sarrus' rule (which has no analogue for $n\ge4$).
📐 Theorem 8.37 — The determinant is the unique normalised alternating multilinear function of the rows

Regard $\det$ as a function of the rows $r_1,\dots,r_n$ of $A$. Then:

  1. (multilinear) $\det$ is linear in each row when the other rows are fixed;
  2. (alternating) if two rows of $A$ are equal, $\det A=0$;
  3. (normalised) $\det I_n=1$.

Any function $D:M_n(\mathbb{F})\to\mathbb{F}$ with (1)–(3) equals $\det$. Consequently: a row swap changes the sign of the determinant, scaling a row by $c$ multiplies it by $c$, a row replacement $R_i\to R_i+cR_j$ does not change it, $\det(cA)=c^n\det A$, and a matrix with a zero row has determinant $0$.

Proof. (1) Each term of the Leibniz sum contains exactly one entry of row $i$, so it is linear in that row. (2) Suppose rows $k\ne l$ are equal and let $\tau$ be the transposition of $k$ and $l$. The map $\sigma\mapsto\sigma\tau$ pairs the permutations into disjoint pairs $\{\sigma,\sigma\tau\}$ (it has no fixed points and is its own inverse). The products $\prod_ia_{i\sigma(i)}$ and $\prod_ia_{i\,\sigma\tau(i)}$ are equal: they differ only by the factors $a_{k\sigma(k)}a_{l\sigma(l)}$ versus $a_{k\sigma(l)}a_{l\sigma(k)}$, which agree because rows $k$ and $l$ are equal. Their signs are opposite, so each pair contributes $0$. (Pairing, rather than "$\det A=-\det A$", makes the proof valid also when $2=0$ in $\mathbb{F}$.) (3) Only $\sigma=\mathrm{id}$ gives a nonzero product.

Row operations. For any $D$ with (1)–(2), write $D(u,v)$ for the value with $u$ in row $i$, $v$ in row $j$ and the other rows fixed. Expanding $0=D(u+v,u+v)$ by linearity in the two slots gives $D(u,v)=-D(v,u)$: a swap changes the sign. Next $D(u+cv,v)=D(u,v)+cD(v,v)$, and the last term is $0$. Scaling is linearity in one row, and $\det(cA)=c^n\det A$ is scaling all $n$ rows. A zero row is $0$ times itself.

Uniqueness. Write $r_i=\sum_ja_{ij}e_j$. Expanding by multilinearity, $D(A)=\sum_{f}a_{1f(1)}\cdots a_{nf(n)}\,D(e_{f(1)},\dots,e_{f(n)})$, the sum over all maps $f:\{1,\dots,n\}\to\{1,\dots,n\}$. If $f$ is not injective two arguments coincide and the term vanishes by (2). If $f=\sigma$ is a permutation, sorting the rows $e_{\sigma(1)},\dots,e_{\sigma(n)}$ into $e_1,\dots,e_n$ by swaps multiplies $D$ by $(-1)^{\text{number of swaps}}=\operatorname{sgn}\sigma$, so $D(e_{\sigma(1)},\dots,e_{\sigma(n)})=\operatorname{sgn}(\sigma)D(I)=\operatorname{sgn}\sigma$. Hence $D(A)$ is the Leibniz sum. ∎

📐 Theorem 8.38 — Transpose, triangular and block triangular matrices
(a) $\det A^T=\det A$; hence every statement of Theorem 8.37 also holds for columns. (b) If $A$ is upper or lower triangular, $\det A=a_{11}a_{22}\cdots a_{nn}$. (c) For square blocks $A\in M_k$, $D\in M_{n-k}$ and any $B$, $$\det\begin{pmatrix}A&B\\0&D\end{pmatrix}=\det A\cdot\det D.$$

Proof. (a) The term of $\sigma$ in $\det A^T$ is $\operatorname{sgn}\sigma\prod_ia_{\sigma(i)i}=\operatorname{sgn}\sigma\prod_ja_{j\sigma^{-1}(j)}$ (reindex by $j=\sigma(i)$); as $\sigma$ runs over $S_n$ so does $\sigma^{-1}$, with the same sign. (b) For upper triangular $A$ a nonzero term needs $\sigma(i)\ge i$ for every $i$; then $\sigma(n)=n$, $\sigma(n-1)=n-1$ and so on downwards, so $\sigma=\mathrm{id}$. Lower triangular follows by (a). (c) Let $M$ be the block matrix. Its entries in rows $k+1,\dots,n$ and columns $1,\dots,k$ are $0$, so a nonzero term of the Leibniz sum needs $\sigma$ to map $\{k+1,\dots,n\}$ into, hence onto, itself; then $\sigma$ maps $\{1,\dots,k\}$ onto itself as well. Such $\sigma$ are exactly the pairs $(\sigma_1,\sigma_2)\in S_k\times S_{n-k}$ acting on the two blocks, with $\operatorname{sgn}\sigma=\operatorname{sgn}\sigma_1\operatorname{sgn}\sigma_2$, and the term factors as (term of $\sigma_1$ in $\det A$)$\times$(term of $\sigma_2$ in $\det D$). Summing gives $\det A\det D$. ∎

📐 Theorem 8.39 — The product rule and the invertibility criterion
For $A,B\in M_n(\mathbb{F})$: $\det(AB)=\det A\cdot\det B$. Moreover $A$ is invertible if and only if $\det A\ne0$, and then $\det(A^{-1})=(\det A)^{-1}$. Similar matrices ($B=P^{-1}AP$) have equal determinants.

Proof. For an elementary matrix $E$, Theorem 8.37 gives $\det E=-1$, $c$ or $1$ (apply the operation to $I$) and $\det(EB)=\det E\cdot\det B$ (apply the operation to $B$). By induction, $\det(E_1\cdots E_kB)=\det E_1\cdots\det E_k\det B$. Let $R=\operatorname{rref}(A)$, so $A=E_1\cdots E_kR$ (Theorem 8.31).

If $\operatorname{rank}A=n$, $R$ has $n$ pivots in $n$ columns, so $R=I$ and $A=E_1\cdots E_k$ is invertible with $\det A=\prod\det E_i\ne0$; then $\det(AB)=\prod\det E_i\cdot\det B=\det A\det B$. If $\operatorname{rank}A\lt n$, $R$ has a zero row, so $\det R=0$ and $\det A=\prod\det E_i\cdot0=0$; also $A$ is not invertible (an invertible $A$ has $n=\operatorname{rank}(AA^{-1})\le\operatorname{rank}A$), and $AB=E_1\cdots E_k(RB)$ where $RB$ has a zero row, so $\det(AB)=0=\det A\det B$. This proves the product rule and the criterion. Finally $\det A\det A^{-1}=\det I=1$, and $\det(P^{-1}AP)=\det P^{-1}\det A\det P=\det A$. ∎

📘 Definition 8.23 — Minors, cofactors and the adjugate

For $A\in M_{m\times n}(\mathbb{F})$, an $r\times r$ minor of $A$ is the determinant of a submatrix formed by $r$ rows and $r$ columns of $A$. For $A\in M_n(\mathbb{F})$ with $n\ge2$, let $A_{(ij)}$ be the $(n-1)\times(n-1)$ matrix obtained by deleting row $i$ and column $j$; then $M_{ij}=\det A_{(ij)}$ is the $(i,j)$ minor and $C_{ij}=(-1)^{i+j}M_{ij}$ the $(i,j)$ cofactor. The adjugate (classical adjoint) of $A$ is the transpose of the cofactor matrix:

$$(\operatorname{adj}A)_{ij}=C_{ji}.$$

For $n=2$: $\operatorname{adj}\begin{pmatrix}a&b\\c&d\end{pmatrix}=\begin{pmatrix}d&-b\\-c&a\end{pmatrix}$. (For $n=1$ one sets $\operatorname{adj}A=(1)$.)

📐 Theorem 8.40 — Laplace (cofactor) expansion
For $A\in M_n(\mathbb{F})$, $n\ge2$, and every fixed $i$ and $j$: $$\det A=\sum_{k=1}^na_{ik}C_{ik}\ \ (\text{along row }i),\qquad\det A=\sum_{k=1}^na_{kj}C_{kj}\ \ (\text{along column }j).$$ "Alien cofactors" give zero: $\sum_ka_{lk}C_{ik}=0$ for $l\ne i$, and $\sum_ka_{kl}C_{kj}=0$ for $l\ne j$.

Proof. By linearity in row $i$, with row $i$ written as $\sum_ka_{ik}e_k$, we get $\det A=\sum_ka_{ik}\det A^{[i,k]}$, where $A^{[i,k]}$ is $A$ with row $i$ replaced by $e_k^T$. In $A^{[i,k]}$, move row $i$ to the top by $i-1$ adjacent row swaps and then column $k$ to the front by $k-1$ adjacent column swaps. The result is $\begin{pmatrix}1&0\\ \ast&A_{(ik)}\end{pmatrix}$, whose determinant is $M_{ik}$ by Theorem 8.38(c) (applied to the transpose). The swaps contribute $(-1)^{i+k-2}=(-1)^{i+k}$, so $\det A^{[i,k]}=C_{ik}$. Expansion along a column is the row expansion of $A^T$. For alien cofactors, $\sum_ka_{lk}C_{ik}$ is the expansion along row $i$ of the matrix obtained from $A$ by replacing row $i$ by row $l$ (the cofactors $C_{ik}$ do not involve row $i$); that matrix has two equal rows, so its determinant is $0$. ∎

📐 Theorem 8.41 — Determinantal rank
For $A\in M_{m\times n}(\mathbb{F})$, $A\ne0$, $\operatorname{rank}A$ is the largest $r$ such that $A$ has a nonzero $r\times r$ minor. In particular, $\operatorname{rank}A\le r-1$ if and only if all $r\times r$ minors of $A$ vanish.

Proof. If the $r\times r$ submatrix $S$ in rows $i_1,\dots,i_r$ and columns $j_1,\dots,j_r$ has $\det S\ne0$, its rows are independent (Theorem 8.39). Then rows $i_1,\dots,i_r$ of $A$ are independent too: a dependence among them would restrict to a dependence among the rows of $S$. So $\operatorname{rank}A\ge r$. Conversely, if $\operatorname{rank}A=r$, choose $r$ independent rows of $A$; they form an $r\times n$ matrix of rank $r$, which therefore has $r$ independent columns (row rank $=$ column rank); these columns form an $r\times r$ submatrix of rank $r$, which is invertible and so has nonzero determinant. ∎

📐 Theorem 8.42 — The adjugate

Let $A\in M_n(\mathbb{F})$, $n\ge2$. Then

$$A\,\operatorname{adj}A=\operatorname{adj}A\,A=(\det A)\,I_n,$$

so if $\det A\ne0$, $A^{-1}=\dfrac{1}{\det A}\operatorname{adj}A$. Moreover:

  1. $\det(\operatorname{adj}A)=(\det A)^{n-1}$ and $\operatorname{adj}(cA)=c^{n-1}\operatorname{adj}A$;
  2. $\operatorname{rank}(\operatorname{adj}A)=n$ if $\operatorname{rank}A=n$; $\ =1$ if $\operatorname{rank}A=n-1$; $\ =0$ if $\operatorname{rank}A\le n-2$;
  3. $\operatorname{adj}(\operatorname{adj}A)=(\det A)^{n-2}A$.

Proof. $(A\operatorname{adj}A)_{il}=\sum_ka_{ik}(\operatorname{adj}A)_{kl}=\sum_ka_{ik}C_{lk}$, which is $\det A$ for $l=i$ (row expansion) and $0$ for $l\ne i$ (alien cofactors). The column versions give $\operatorname{adj}A\,A=(\det A)I$. (1) Taking determinants, $\det A\cdot\det(\operatorname{adj}A)=\det((\det A)I)=(\det A)^n$; if $\det A\ne0$, divide. If $\det A=0$ and $\operatorname{adj}A$ were invertible, then $A=A\operatorname{adj}A(\operatorname{adj}A)^{-1}=0$, whose adjugate is $0$ (as $n\ge2$) — a contradiction; so $\det\operatorname{adj}A=0=(\det A)^{n-1}$. Every cofactor of $cA$ is an $(n-1)\times(n-1)$ determinant of $c$ times a submatrix, hence $c^{n-1}$ times the cofactor of $A$.

(2) If $\operatorname{rank}A=n$, $\det\operatorname{adj}A\ne0$ by (1). If $\operatorname{rank}A\le n-2$, every $(n-1)\times(n-1)$ minor vanishes (Theorem 8.41), so $\operatorname{adj}A=0$. If $\operatorname{rank}A=n-1$, then $A\operatorname{adj}A=0$, so $\operatorname{rank}A+\operatorname{rank}\operatorname{adj}A\le n$ (Theorem 8.36(1)) and $\operatorname{rank}\operatorname{adj}A\le1$; some $(n-1)\times(n-1)$ minor is nonzero (Theorem 8.41), so $\operatorname{adj}A\ne0$ and the rank is exactly $1$.

(3) If $\det A\ne0$: $\operatorname{adj}A=(\det A)A^{-1}$, so the inverse formula applied to the invertible matrix $\operatorname{adj}A$ and (1) give $$\operatorname{adj}(\operatorname{adj}A)=\det(\operatorname{adj}A)\,(\operatorname{adj}A)^{-1}=(\det A)^{n-1}\cdot\frac{A}{\det A}=(\det A)^{n-2}A.$$ If $\det A=0$ and $n\ge3$: by (2), $\operatorname{rank}\operatorname{adj}A\le1\le n-2$, so $\operatorname{adj}(\operatorname{adj}A)=0=(\det A)^{n-2}A$. For $n=2$, applying the $2\times2$ formula twice returns $A$, and $(\det A)^0=1$. ∎

📐 Theorem 8.43 — Block determinants and Sylvester's determinant identity

(a) Schur complement. If $A\in M_k(\mathbb{F})$ is invertible, then $\det\begin{pmatrix}A&B\\C&D\end{pmatrix}=\det A\cdot\det(D-CA^{-1}B)$. If in addition $AC=CA$, this equals $\det(AD-CB)$.

(b) Sylvester's determinant identity. For $A\in M_{m\times n}(\mathbb{F})$ and $B\in M_{n\times m}(\mathbb{F})$, $\det(I_m+AB)=\det(I_n+BA)$. In particular, for column vectors $u,v\in\mathbb{F}^n$,

$$\det(I_n+uv^T)=1+v^Tu,$$

and, for invertible $A$, $\det(A+uv^T)=\det A\,(1+v^TA^{-1}u)$ (the matrix determinant lemma).

Proof. (a) Multiply out to check $$\begin{pmatrix}A&B\\C&D\end{pmatrix}=\begin{pmatrix}I&0\\CA^{-1}&I\end{pmatrix}\begin{pmatrix}A&B\\0&D-CA^{-1}B\end{pmatrix},$$ and take determinants using Theorem 8.38(c) and the product rule. If $AC=CA$ then $CA^{-1}=A^{-1}C$, so $ACA^{-1}=C$ and, by the product rule, $$\det A\det(D-CA^{-1}B)=\det(AD-CB).$$ (b) Let $M=\begin{pmatrix}I_m&-A\\B&I_n\end{pmatrix}$. Direct multiplication gives the two factorisations $$M=\begin{pmatrix}I_m&0\\B&I_n\end{pmatrix}\begin{pmatrix}I_m&-A\\0&I_n+BA\end{pmatrix},$$ $$M=\begin{pmatrix}I_m+AB&-A\\0&I_n\end{pmatrix}\begin{pmatrix}I_m&0\\B&I_n\end{pmatrix}.$$ The first gives $\det M=\det(I_n+BA)$, the second $\det M=\det(I_m+AB)$. With $A=u$ ($n\times1$) and $B=v^T$ ($1\times n$): $\det(I_n+uv^T)=\det(1+v^Tu)$. Finally $A+uv^T=A(I+(A^{-1}u)v^T)$. ∎

✏️ Example 4 — Two determinants every candidate must know
(a) Prove the Vandermonde formula $$V(x_1,\dots,x_n)=\det\begin{pmatrix}1&x_1&x_1^2&\cdots&x_1^{n-1}\\ \vdots&&&&\vdots\\1&x_n&x_n^2&\cdots&x_n^{n-1}\end{pmatrix}=\prod_{1\le i\lt j\le n}(x_j-x_i).$$ (b) Show that $\det(aI_n+bJ_n)=a^{n-1}(a+nb)$, where $J_n$ is the all-ones matrix, and deduce the determinant of the $n\times n$ matrix with $x$ on the diagonal and $1$ elsewhere.
(a) Column operations For $j=n,n-1,\dots,2$ (in this order) replace column $j$ by column $j$ minus $x_1$ times column $j-1$; the determinant is unchanged. Row $i$ becomes $\big(1,\ x_i-x_1,\ x_i(x_i-x_1),\ \dots,\ x_i^{n-2}(x_i-x_1)\big)$; in particular row $1$ becomes $(1,0,\dots,0)$.
(a) Expand and induct Expanding along row $1$ leaves the $(n-1)\times(n-1)$ matrix with rows $(x_i-x_1)\big(1,x_i,\dots,x_i^{n-2}\big)$, $i=2,\dots,n$. Taking the factor $x_i-x_1$ out of each row: $$V(x_1,\dots,x_n)=\prod_{i=2}^n(x_i-x_1)\cdot V(x_2,\dots,x_n).$$ With $V(x_n)=1$, induction gives the product over all pairs $i\lt j$. In particular $V\ne0$ iff the $x_i$ are distinct — the reason why a polynomial of degree $\lt n$ is determined by its values at $n$ distinct points.
(b) $J_n=\mathbf 1\mathbf 1^T$ and $\mathbf 1^T\mathbf 1=n$. For $a\ne0$, Theorem 8.43(b): $\det(aI+b\mathbf 1\mathbf 1^T)=a^n\det\!\big(I+\tfrac ba\mathbf 1\mathbf 1^T\big)=a^n\big(1+\tfrac{nb}{a}\big)=a^{n-1}(a+nb)$. Both sides are polynomials in $a$ that agree for all $a\ne0$ (infinitely many values when $\mathbb{F}$ is infinite), so they agree at $a=0$ too. (Directly: for $a=0$ and $n\ge2$, $bJ_n$ has rank $\le1$ and determinant $0$.)
Deduction $x$ on the diagonal and $1$ elsewhere is $(x-1)I+J$: determinant $(x-1)^{n-1}(x+n-1)$. Check $n=2$: $x^2-1=(x-1)(x+1)$. ✓
✏️ Example 5 — Adjugates in practice
Let $A=\begin{pmatrix}2&1&0\\1&3&1\\0&1&2\end{pmatrix}$ and $B=\begin{pmatrix}1&2&3\\4&5&6\\7&8&9\end{pmatrix}$. Compute $\operatorname{adj}A$, $A^{-1}$, $\det(\operatorname{adj}A)$ and $\operatorname{adj}(\operatorname{adj}A)$; then compute $\operatorname{adj}B$, its rank, and explain why its columns lie in $N(B)$.
Cofactors of $A$ $C_{11}=6-1=5$, $C_{12}=-(2-0)=-2$, $C_{13}=1$, $C_{21}=-(2-0)=-2$, $C_{22}=4$, $C_{23}=-(2-0)=-2$, $C_{31}=1$, $C_{32}=-(2-0)=-2$, $C_{33}=6-1=5$. Expanding along row 1: $\det A=2\cdot5+1\cdot(-2)+0=8$.
Inverse The cofactor matrix is symmetric (as $A$ is), so $$\operatorname{adj}A=\begin{pmatrix}5&-2&1\\-2&4&-2\\1&-2&5\end{pmatrix},\qquad A^{-1}=\frac18\operatorname{adj}A.$$ Check one entry of $AA^{-1}$: row 1 of $A$ times column 1 of $\operatorname{adj}A$ is $10-2+0=8$. ✓
Identities $\det(\operatorname{adj}A)=8^{3-1}=64$ and $\operatorname{adj}(\operatorname{adj}A)=8^{3-2}A=8A$ (Theorem 8.42).
Singular $B$ $R_2-R_1=(3,3,3)$ and $R_3-R_2=(3,3,3)$, so $\operatorname{rank}B=2=n-1$ and $\operatorname{adj}B$ has rank $1$. Computing: $$\operatorname{adj}B=\begin{pmatrix}-3&6&-3\\6&-12&6\\-3&6&-3\end{pmatrix}=-3\begin{pmatrix}1\\-2\\1\end{pmatrix}\begin{pmatrix}1&-2&1\end{pmatrix}.$$ Since $B\operatorname{adj}B=(\det B)I=0$, every column of $\operatorname{adj}B$ lies in $N(B)$, which is the line spanned by $(1,-2,1)^T$. This is a fast way to find the null vector of a corank-one matrix.

Linear Systems: Rouché–Capelli and Cramer's Rule

📘 Definition 8.24 — Linear systems
A system of $m$ linear equations in $n$ unknowns over $\mathbb{F}$ is $Ax=b$ with $A\in M_{m\times n}(\mathbb{F})$ (the coefficient matrix), $b\in\mathbb{F}^m$, and augmented matrix $[A\mid b]\in M_{m\times(n+1)}(\mathbb{F})$. It is homogeneous if $b=0$, and consistent if it has at least one solution. Row operations on $[A\mid b]$ do not change the solution set, because they replace $Ax=b$ by $PAx=Pb$ with $P$ invertible.
📐 Theorem 8.44 — Rouché–Capelli (Kronecker–Capelli) theorem

Let $A\in M_{m\times n}(\mathbb{F})$, $b\in\mathbb{F}^m$ and $r=\operatorname{rank}A$.

  1. $Ax=b$ is consistent if and only if $\operatorname{rank}A=\operatorname{rank}[A\mid b]$, i.e. iff $b\in C(A)$.
  2. If $x_0$ is one solution, the solution set is $x_0+N(A)=\{x_0+z:Az=0\}$, an affine subspace of dimension $n-r$, parametrised by the $n-r$ free variables.
  3. A consistent system has a unique solution iff $r=n$. If $r\lt n$ it has infinitely many solutions when $\mathbb{F}$ is infinite, and exactly $q^{n-r}$ solutions when $\mathbb{F}=\mathbb{F}_q$.
  4. A homogeneous system with more unknowns than equations ($n\gt m$) has a nonzero solution.

Proof. (1) $Ax=x_1a_1+\cdots+x_na_n$, so a solution exists iff $b$ is a combination of the columns, i.e. $b\in C(A)$. Since $C(A)\subseteq C([A\mid b])=C(A)+\operatorname{span}\{b\}$, the two spaces are equal — equivalently have equal dimension — iff $b\in C(A)$. (2) If $Ax_0=b$, then $Ax=b\iff A(x-x_0)=0\iff x-x_0\in N(A)$; and $\dim N(A)=n-r$ (Theorem 8.32(4)). (3) $z\mapsto x_0+z$ is a bijection from $N(A)\cong\mathbb{F}^{n-r}$ onto the solution set; $\mathbb{F}^{n-r}$ is a single point iff $n=r$, is infinite if $\mathbb{F}$ is infinite and $n\gt r$, and has $q^{n-r}$ elements over $\mathbb{F}_q$. (4) $b=0$ is always consistent and $r\le m\lt n$. ∎

In echelon terms: the system is inconsistent exactly when the RREF of $[A\mid b]$ has a pivot in the last column, i.e. a row $(0\ \cdots\ 0\mid1)$, which reads $0=1$.

📐 Theorem 8.45 — Cramer's rule
If $A\in M_n(\mathbb{F})$ is invertible and $b\in\mathbb{F}^n$, the unique solution of $Ax=b$ is $$x_i=\frac{\det A_i}{\det A},\qquad i=1,\dots,n,$$ where $A_i$ is $A$ with its $i$-th column replaced by $b$.

Proof. Let $x$ be the solution and let $X_i$ be the identity matrix with its $i$-th column replaced by $x$. Then $AX_i$ has columns $Ae_1,\dots,Ax,\dots,Ae_n$, i.e. $AX_i=A_i$. Expanding $\det X_i$ along row $i$ (whose only nonzero entry is $x_i$, at the diagonal position, with minor $\det I_{n-1}=1$) gives $\det X_i=x_i$. The product rule gives $\det A\cdot x_i=\det A_i$. ∎

Cramer's rule is a theoretical tool — it shows, for instance, that the solution depends continuously (indeed rationally) on the entries of $A$ and $b$ — but for computation elimination is far cheaper: about $\tfrac23n^3$ operations against $(n+1)$ determinants.

📐 Theorem 8.46 — The invertible matrix theorem

For $A\in M_n(\mathbb{F})$ the following are equivalent:

Algebra(1) $A$ is invertible; (2) $A$ has a left inverse ($BA=I$); (3) $A$ has a right inverse ($AB=I$); (4) $A$ is a product of elementary matrices.
Numbers(5) $\det A\ne0$; (6) $\operatorname{rank}A=n$; (7) $\operatorname{rref}(A)=I_n$.
Systems(8) $N(A)=\{0\}$; (9) $Ax=b$ is solvable for every $b$; (10) $Ax=b$ has exactly one solution for some $b$.
Vectors(11) the columns of $A$ form a basis of $\mathbb{F}^n$; (12) the rows of $A$ form a basis of $\mathbb{F}^n$.

Proof. (1)⇔(5) is Theorem 8.39; (6)⇔(7) because an $n\times n$ RREF with $n$ pivots is $I_n$; (7)⇒(4) by Theorem 8.31 ($A=P\cdot I$ with $P$ a product of elementary matrices), (4)⇒(1) is immediate, and (1)⇒(6) was shown in the proof of Theorem 8.39. By rank–nullity, (6)⇔(8); (6)⇔(9) because (9) says $C(A)=\mathbb{F}^n$; (8)⇔(10) by Theorem 8.44(2) (a consistent system has a unique solution iff $N(A)=0$, and $b=0$ is consistent). (6) says the $n$ columns span an $n$-dimensional $C(A)$, which for $n$ vectors in $\mathbb{F}^n$ is (11) (§8.1); (12) is (11) for $A^T$, and $\operatorname{rank}A^T=\operatorname{rank}A$. Finally (2)⇒(6): $n=\operatorname{rank}(BA)\le\operatorname{rank}A$; (3)⇒(6) likewise; and (1)⇒(2),(3). In particular a one-sided inverse of a square matrix is automatically two-sided. ∎

🧭 Problem-solving strategy — systems with parameters
  1. Row-reduce the augmented matrix without dividing by expressions that might vanish (use replacements and swaps; postpone scaling).
  2. Read off the last pivot candidate, typically an entry like $(a-2)$ with right-hand side $(b-4)$. Then split: entry $\ne0$ ⇒ $\operatorname{rank}A=n$, unique solution (Cramer gives it as a rational function of the parameters); entry $=0$ and right side $\ne0$ ⇒ $\operatorname{rank}A\lt\operatorname{rank}[A\mid b]$, no solution; both $=0$ ⇒ infinitely many, with $n-r$ free parameters.
  3. For a square system, $\det A$ is a quick first filter: the unique-solution case is exactly $\det A\ne0$. But when $\det A=0$, look at ranks — do not conclude anything from $\det A_i=0$ alone (pitfall 6 below).
✏️ Example 6 — A system with two parameters
For which real $a,b$ is the system $$x+2y-z=3,\qquad 2x+5y+z=7,\qquad x+3y+az=b$$ inconsistent, uniquely solvable, or solvable with infinitely many solutions? Give the solutions, and solve the case $a=3$, $b=6$ by Cramer's rule.
Reduce Start from $$[A\mid b]=\left(\begin{array}{ccc|c}1&2&-1&3\\2&5&1&7\\1&3&a&b\end{array}\right).$$ After $R_2\to R_2-2R_1$ and $R_3\to R_3-R_1$: $$\left(\begin{array}{ccc|c}1&2&-1&3\\0&1&3&1\\0&1&a+1&b-3\end{array}\right),$$ and after $R_3\to R_3-R_2$: $$\left(\begin{array}{ccc|c}1&2&-1&3\\0&1&3&1\\0&0&a-2&b-4\end{array}\right).$$ No division was needed, and $\det A=1\cdot1\cdot(a-2)=a-2$ (replacements do not change the determinant).
Cases $a\ne2$: rank $3$, unique solution $z=\dfrac{b-4}{a-2}$, $y=1-3z$, $x=3-2y+z=1+7z$. $a=2$, $b\ne4$: the last row reads $0=b-4\ne0$; $\operatorname{rank}A=2\lt3=\operatorname{rank}[A\mid b]$: no solution. $a=2$, $b=4$: rank $2=\operatorname{rank}[A\mid b]$, one free variable: $(x,y,z)=(1,1,0)+t(7,-3,1)$, $t\in\mathbb{R}$.
Cramer at $a=3,b=6$ $\det A=1$. $\det A_1=\det\begin{pmatrix}3&2&-1\\7&5&1\\6&3&3\end{pmatrix}=3(15-3)-2(21-6)-(21-30)=36-30+9=15$, $\det A_2=\det\begin{pmatrix}1&3&-1\\2&7&1\\1&6&3\end{pmatrix}=(21-6)-3(6-1)-(12-7)=15-15-5=-5$, $\det A_3=\det\begin{pmatrix}1&2&3\\2&5&7\\1&3&6\end{pmatrix}=(30-21)-2(12-7)+3(6-5)=9-10+3=2$. So $(x,y,z)=(15,-5,2)$, agreeing with $z=\tfrac{2}{1}$, $y=1-6$, $x=1+14$.
Check $15-10-2=3$, $30-25+2=7$, $15-15+6=6$. ✓ In the infinite case: $7-6-1=0$, $14-15+1=0$, $7-9+2=0$, so the direction lies in $N(A)$. ✓
Interactive 2 — Two Pictures of $Ax=b$: Lines, Columns and Cramer's Rule

The system is $2x+y=4$, $x+ty=s$. Left (row picture): each equation is a line and a solution is a common point. Right (column picture): a solution is a pair of weights with $x\,a_1+y\,a_2=b$, where $a_1=(2,1)$, $a_2=(1,t)$, $b=(4,s)$. The purple parallelogram has signed area $\det A=2t-1$, the green one (spanned by $b$ and $a_2$) has signed area $\det A_1$; Cramer's rule says $x$ is their ratio. Press Play to sweep $t$ through the singular value $t=\tfrac12$, or set $t=0.5$ and then $s=2$.

1.505.00
det A—
rank A | rank [A|b]—
det A₁ , det A₂—
solution (x, y)—

Special Matrices

📘 Definition 8.25 — Special classes of square matrices

A matrix $A\in M_n(\mathbb{F})$ is

Triangularupper triangular if $a_{ij}=0$ for $i\gt j$, strictly upper triangular if $a_{ij}=0$ for $i\ge j$; lower triangular similarly; diagonal if both upper and lower triangular.
Symmetrysymmetric if $A^T=A$; skew-symmetric if $A^T=-A$; over $\mathbb{C}$, Hermitian if $A^*=A$.
Orthogonal / unitaryorthogonal ($\mathbb{F}=\mathbb{R}$) if $A^TA=I$; unitary ($\mathbb{F}=\mathbb{C}$) if $A^*A=I$; a permutation matrix has exactly one $1$ in each row and column, other entries $0$.
Powersnilpotent if $A^k=0$ for some $k\ge1$ (the least such $k$ is the index); idempotent if $A^2=A$; involutory if $A^2=I$.
📐 Theorem 8.47 — Triangular matrices
(a) Products of upper triangular matrices are upper triangular, and the diagonal of $AB$ is $(a_{11}b_{11},\dots,a_{nn}b_{nn})$. (b) An upper triangular $A$ is invertible iff every $a_{ii}\ne0$, and then $A^{-1}$ is upper triangular with diagonal entries $a_{ii}^{-1}$. (c) A strictly upper triangular $T\in M_n(\mathbb{F})$ satisfies $T^n=0$.

Proof. (a) $(AB)_{ij}=\sum_ka_{ik}b_{kj}$, and a term can be nonzero only if $i\le k$ and $k\le j$. For $i\gt j$ there is no such $k$; for $i=j$ only $k=i$ survives. (b) $\det A=\prod a_{ii}$ (Theorem 8.38(b)), so invertibility is $\prod a_{ii}\ne0$. Let $\mathcal{U}$ be the space of upper triangular matrices. If $A\in\mathcal{U}$ is invertible, the linear map $X\mapsto AX$ sends $\mathcal{U}$ into $\mathcal{U}$ by (a), and it is injective ($AX=0\Rightarrow X=0$); as $\dim\mathcal{U}\lt\infty$ it is also surjective, so $AX=I$ for some $X\in\mathcal{U}$, and $X=A^{-1}$. By (a) the diagonal of $AA^{-1}=I$ is $(a_{ii}(A^{-1})_{ii})$, so $(A^{-1})_{ii}=a_{ii}^{-1}$. (c) Let $V_j=\operatorname{span}\{e_1,\dots,e_j\}$ ($V_0=0$). Column $j$ of $T$ has nonzero entries only in rows $\lt j$, so $Te_j\in V_{j-1}$ and $T(V_j)\subseteq V_{j-1}$. Hence $T^n(\mathbb{F}^n)=T^n(V_n)\subseteq V_0=0$. ∎

📐 Theorem 8.48 — Nilpotent matrices

Let $N\in M_n(\mathbb{F})$ be nilpotent of index $k$. Then:

  1. $k\le n$, i.e. $N^n=0$;
  2. $N$ is similar to a strictly upper triangular matrix;
  3. $\det N=0$, $\operatorname{tr}N=0$ and $\det(I+cN)=1$ for every scalar $c$;
  4. $I-N$ is invertible, with $(I-N)^{-1}=I+N+N^2+\cdots+N^{k-1}$;
  5. if $N$ is similar to a diagonal matrix, then $N=0$.

Parts (1) and (4) were proved for nilpotent maps in §8.2 (via the strictly increasing chain of kernels); the new information here is the triangular form and what it says about traces and determinants.

Proof. (1) also follows from Theorem 8.36(3). (2) Let $K_j=N(N^j)$, so $0=K_0\subseteq K_1\subseteq\cdots\subseteq K_k=\mathbb{F}^n$. Choose a basis of $K_1$, extend it to a basis of $K_2$, and so on (§8.1), obtaining a basis $v_1,\dots,v_n$ of $\mathbb{F}^n$ in which each $K_j$ is spanned by an initial segment. If $v_i\in K_j\setminus K_{j-1}$, then $N^{j-1}(Nv_i)=N^jv_i=0$, so $Nv_i\in K_{j-1}$, which is spanned by basis vectors that come before $v_i$. With $P=[v_1\ \cdots\ v_n]$, the $i$-th column of $P^{-1}NP$ is the coordinate vector of $Nv_i$, which has nonzero entries only above the diagonal: $P^{-1}NP$ is strictly upper triangular (change of basis, §8.2). (3) $\det N=0$ since $(\det N)^k=\det N^k=0$. Similar matrices have equal traces ($\operatorname{tr}(P^{-1}NP)=\operatorname{tr}(NPP^{-1})$ by $\operatorname{tr}(XY)=\operatorname{tr}(YX)$) and determinants, and $P^{-1}(I+cN)P=I+cT$ is upper triangular with $1$s on the diagonal; so $\operatorname{tr}N=\operatorname{tr}T=0$ and $\det(I+cN)=1$. (4) $(I-N)(I+N+\cdots+N^{k-1})=I-N^k=I$, and a right inverse of a square matrix is an inverse (Theorem 8.46). (5) If $N=PDP^{-1}$ with $D$ diagonal, then $D^k=P^{-1}N^kP=0$, so each diagonal entry $d$ of $D$ has $d^k=0$, i.e. $d=0$; thus $D=0$ and $N=0$. ∎

📐 Theorem 8.49 — Idempotent matrices

Let $P\in M_n(\mathbb{F})$ with $P^2=P$ and $r=\operatorname{rank}P$. Then:

  1. $I-P$ is idempotent, $P(I-P)=(I-P)P=0$, and $N(P)=C(I-P)$;
  2. $\mathbb{F}^n=C(P)\oplus N(P)$, and $Px=x$ for $x\in C(P)$: $P$ is the projection onto $C(P)$ along $N(P)$;
  3. $P$ is similar to $\begin{pmatrix}I_r&0\\0&0\end{pmatrix}$; hence $\operatorname{tr}P=r\cdot1_{\mathbb{F}}$ (so $\operatorname{tr}P=\operatorname{rank}P$ when $\mathbb{F}\supseteq\mathbb{Q}$), and $\det P=0$ unless $P=I$;
  4. $\operatorname{rank}P+\operatorname{rank}(I-P)=n$.

Proof. Parts (1)–(3), apart from the determinant, are the theorem on projections of §8.2 applied to the map $x\mapsto Px$; we recall the key steps. (1) $(I-P)^2=I-2P+P^2=I-P$ and $P(I-P)=P-P^2=0$, similarly on the other side. If $x\in N(P)$ then $x=(I-P)x\in C(I-P)$; conversely $P(I-P)y=0$. (2) Every $x$ is $Px+(I-P)x$ with $Px\in C(P)$ and $(I-P)x\in N(P)$; if $y=Pz$ also lies in $N(P)$, then $y=P^2z=Py=0$. (3) A basis of $C(P)$ followed by a basis of $N(P)$ is a basis of $\mathbb{F}^n$ in which the matrix of $P$ is $\operatorname{diag}(I_r,0)$. Trace and determinant are similarity invariants; the determinant is $0$ unless $r=n$, and if $r=n$ then $P$ is invertible and $P=P^{-1}P^2=P^{-1}P=I$. (4) By (1), $\operatorname{rank}(I-P)=\dim C(I-P)=\dim N(P)=n-r$. (Exercise II.4 gives a second proof using only rank inequalities.) ∎

📐 Theorem 8.50 — Orthogonal and unitary matrices

For $Q\in M_n(\mathbb{R})$ the following are equivalent: (i) $Q^TQ=I$; (ii) $QQ^T=I$; (iii) the columns of $Q$ are orthonormal; (iv) the rows of $Q$ are orthonormal; (v) $(Qx)\cdot(Qy)=x\cdot y$ for all $x,y\in\mathbb{R}^n$; (vi) $\|Qx\|=\|x\|$ for all $x$. For such $Q$: $Q^{-1}=Q^T$, $\det Q=\pm1$, and products and inverses of orthogonal matrices are orthogonal. Every $2\times2$ orthogonal matrix is a rotation $\begin{pmatrix}\cos\theta&-\sin\theta\\\sin\theta&\cos\theta\end{pmatrix}$ ($\det=1$) or a reflection $\begin{pmatrix}\cos\theta&\sin\theta\\\sin\theta&-\cos\theta\end{pmatrix}$ ($\det=-1$). For complex unitary $U$ the same equivalences hold with $U^*$ and the Hermitian dot product, and $|\det U|=1$.

Proof. (i)⇔(ii): a one-sided inverse of a square matrix is two-sided (Theorem 8.46). (i)⇔(iii): $(Q^TQ)_{ij}=q_i\cdot q_j$ where $q_i$ are the columns; (ii)⇔(iv) in the same way with rows. (i)⇒(v): $(Qx)\cdot(Qy)=x^TQ^TQy=x^Ty$. (v)⇒(i): $(Q^TQ)_{ij}=(Qe_i)\cdot(Qe_j)$, which equals $e_i\cdot e_j=\delta_{ij}$. (v)⇒(vi) with $y=x$; (vi)⇒(v) by polarisation: $2\,x\cdot y=\|x+y\|^2-\|x\|^2-\|y\|^2$. Next, $(\det Q)^2=\det Q^T\det Q=\det I=1$. If $Q_1,Q_2$ are orthogonal, then $(Q_1Q_2)^T(Q_1Q_2)$ equals $Q_2^T(Q_1^TQ_1)Q_2=I$, and $Q^{-1}=Q^T$ is orthogonal because $(Q^T)^TQ^T=QQ^T=I$ by (ii). For $n=2$, the first column is a unit vector $(\cos\theta,\sin\theta)^T$ and the second is a unit vector orthogonal to it, i.e. $\pm(-\sin\theta,\cos\theta)^T$; the two signs give the two forms. The unitary case is identical with $\overline{\det U}\det U=|\det U|^2=1$. ∎

✏️ Example 7 — Special matrices: prove or disprove
(a) The sum of two nilpotent matrices is nilpotent. (b) If $A\in M_n(\mathbb{F})$ and $A^3=A$, then $\operatorname{rank}A=\operatorname{rank}A^2$. (c) Every real skew-symmetric matrix of odd order is singular. (d) The product of two idempotent matrices is idempotent. (e) If $A\in M_n(\mathbb{R})$ and $A^2=I$, then $A=\pm I$.
(a) False $E_{12}=\begin{pmatrix}0&1\\0&0\end{pmatrix}$ and $E_{21}$ are nilpotent, but $(E_{12}+E_{21})^2=I$, so their sum is invertible. (If $NM=MN$ the statement is true: expand $(N+M)^{k+l}$ by the binomial theorem.)
(b) True $\operatorname{rank}A^2\le\operatorname{rank}A$, and $A=A^2\cdot A$ gives $\operatorname{rank}A\le\operatorname{rank}A^2$.
(c) True $\det A=\det A^T=\det(-A)=(-1)^n\det A=-\det A$ for odd $n$, so $2\det A=0$ and $\det A=0$. The division by $2$ matters: over $\mathbb{F}_2$, where $-1=1$, the $1\times1$ matrix $(1)$ is skew-symmetric with determinant $1$.
(d) False $P=\begin{pmatrix}1&0\\0&0\end{pmatrix}$ and $Q=\tfrac12\begin{pmatrix}1&1\\1&1\end{pmatrix}$ are idempotent, but $PQ=\tfrac12\begin{pmatrix}1&1\\0&0\end{pmatrix}$ has $(PQ)^2=\tfrac14\begin{pmatrix}1&1\\0&0\end{pmatrix}\ne PQ$. (If $PQ=QP$ then $(PQ)^2=P^2Q^2=PQ$.)
(e) False $A=\operatorname{diag}(1,-1)$. What is true: $\det A=\pm1$, and $E=\tfrac12(I+A)$ is idempotent (since $E^2=\tfrac14(I+2A+A^2)=\tfrac12(I+A)$), so $A=2E-I$ is similar to $\operatorname{diag}(I_r,-I_{n-r})$ by Theorem 8.49(3).
⚠️ Counterexamples and pitfalls
  1. $AB$ and $BA$ can have different ranks. $A=E_{12}$, $B=E_{11}$ in $M_2$: $AB=0$, $BA=E_{12}$. They agree when one factor is invertible.
  2. Row operations change the column space. $\begin{pmatrix}1\\1\end{pmatrix}\sim\begin{pmatrix}1\\0\end{pmatrix}$ but the column spaces differ. Row operations preserve the row space, the null space and the linear relations among columns — so take the pivot columns of $A$, not of its RREF.
  3. $\operatorname{rank}(A^TA)=\operatorname{rank}A$ is a real-number fact. It fails over $\mathbb{C}$ ($A=(1,i)^T$, $A^TA=0$) and over $\mathbb{F}_2$ ($A=(1,1)^T$); over $\mathbb{C}$ use $A^*A$.
  4. The rank can depend on the field — but not for subfields. $\begin{pmatrix}1&1&0\\0&1&1\\1&0&1\end{pmatrix}$ has determinant $2$: rank $3$ over $\mathbb{Q},\mathbb{R},\mathbb{C}$, rank $2$ over $\mathbb{F}_2$ (the rows sum to $0$). A rational matrix has the same rank over $\mathbb{Q}$, $\mathbb{R}$ and $\mathbb{C}$.
  5. The determinant is not additive, and scalars come out to the $n$-th power. $\det(I+I)=2^n\ne2$; $\det(cA)=c^n\det A$; $\det(\operatorname{adj}A)=(\det A)^{n-1}$, not $\det A$.
  6. Cramer's rule says nothing when $\det A=0$. For $x+y+z=1$, $x+y+z=2$, $x+y+z=3$, $\det A=0$ and every $\det A_i=0$ (two equal columns), yet the system is inconsistent. Use ranks (Rouché–Capelli).
  7. The rank of a sum can drop below both ranks. $\operatorname{rank}(A+(-A))=0$; only $\operatorname{rank}(A+B)\ge|\operatorname{rank}A-\operatorname{rank}B|$ holds. In particular "$\operatorname{rank}(A+B)\ge\operatorname{rank}A+\operatorname{rank}B-n$" is false.
  8. Nilpotent matrices do not form a subspace. $E_{12}+E_{21}$ is an involution. Nonzero nilpotent matrices exist ($E_{12}$), and the only diagonalisable nilpotent matrix is $0$.
  9. "Trace equals rank" for idempotents needs characteristic $0$. Over $\mathbb{F}_2$, $I_2$ is idempotent of rank $2$ and trace $0$.
  10. Odd skew-symmetric matrices are singular — except in characteristic $2$. Over $\mathbb{F}_2$, $(1)$ is skew-symmetric and invertible.
  11. $\det Q=\pm1$ does not make $Q$ orthogonal. $\begin{pmatrix}1&1\\0&1\end{pmatrix}$ has determinant $1$ but is not orthogonal (it stretches $e_2$ to length $\sqrt2$).
  12. One-sided inverses of non-square matrices are not two-sided. $A=\begin{pmatrix}1\\0\end{pmatrix}$ has $A^TA=(1)$ but $AA^T=\operatorname{diag}(1,0)\ne I_2$. For square matrices, one side suffices.

Exercises

I
Row reduction and rank.
  • 1 Find $\operatorname{rref}(A)$, $\operatorname{rank}A$ and bases of the row space, column space and null space of $A=\begin{pmatrix}1&2&1&0\\2&4&3&1\\3&6&4&1\end{pmatrix}$.
  • 2 Find the rank of $\begin{pmatrix}1&t&t\\t&1&t\\t&t&1\end{pmatrix}$ for every real $t$.
  • 3 Write $\begin{pmatrix}1&2\\3&4\end{pmatrix}$ as a product of elementary matrices.
  • 4 For $n\ge2$ find the rank of the $n\times n$ matrices with entries (a) $i-j$; (b) $ij$; (c) $(-1)^{i+j}$; (d) $i^2-j^2$.
  • 5 Prove directly that $\operatorname{rank}A=1$ iff $A=uv^T$ with $u,v$ nonzero, and show that then $A^2=(v^Tu)A$.
  • 6 Find the rank of the $n\times n$ matrix $\big(\sin(i+j)\big)$ for $n\ge2$.
  • 7 Prove that row-equivalent matrices have the same null space. Do they have the same column space?
  • 8 Find the rank of $\begin{pmatrix}1&1&0\\0&1&1\\1&0&1\end{pmatrix}$ over $\mathbb{R}$ and over $\mathbb{F}_2$.
1 $R_2-2R_1=(0,0,1,1)$, $R_3-3R_1=(0,0,1,1)$, then $R_3-R_2=0$ and $R_1-R_2$: $\operatorname{rref}(A)=\begin{pmatrix}1&2&0&-1\\0&0&1&1\\0&0&0&0\end{pmatrix}$, rank $2$. Row space: $(1,2,0,-1),(0,0,1,1)$. Column space: columns 1 and 3 of $A$, $(1,2,3)^T,(1,3,4)^T$. Null space ($x_2=s$, $x_4=t$): $(-2,1,0,0)^T,(1,0,-1,1)^T$; nullity $2$.
2 This is $(1-t)I+tJ$, so by Example 4(b) $\det=(1-t)^2(1+2t)$. Rank $3$ for $t\ne1,-\tfrac12$; at $t=1$ all entries are $1$: rank $1$; at $t=-\tfrac12$ the determinant vanishes but the top-left $2\times2$ minor is $1-\tfrac14\ne0$: rank $2$.
3 $R_2\to R_2-3R_1$, then $R_2\to-\tfrac12R_2$, then $R_1\to R_1-2R_2$ reduce $A$ to $I$. Inverting the three operations: $A=\begin{pmatrix}1&0\\3&1\end{pmatrix}\begin{pmatrix}1&0\\0&-2\end{pmatrix}\begin{pmatrix}1&2\\0&1\end{pmatrix}$. Check: the product of the first two is $\begin{pmatrix}1&0\\3&-2\end{pmatrix}$, and times the third gives $\begin{pmatrix}1&2\\3&4\end{pmatrix}$. ✓
4 (a) $u\mathbf 1^T-\mathbf 1u^T$: rank $\le2$, and columns 1, 2 are $(0,1,2,\dots)^T$ and $(-1,0,1,\dots)^T$, independent: rank $2$. (b) $uu^T$: rank $1$. (c) $ww^T$ with $w=((-1)^i)$: rank $1$. (d) $u^{(2)}\mathbf 1^T-\mathbf 1u^{(2)T}$: rank $2$ (columns 1 and 2 are $(0,3,8,\dots)^T$ and $(-3,0,5,\dots)^T$, independent).
5 If $\operatorname{rank}A=1$, $C(A)=\operatorname{span}\{u\}$ for some $u\ne0$, so column $j$ is $v_ju$ and $A=uv^T$ with $v=(v_j)\ne0$ (else $A=0$). Conversely see Theorem 8.33(3). Then $A^2=u(v^Tu)v^T=(v^Tu)A$, since $v^Tu$ is a scalar.
6 $\sin(i+j)=\sin i\cos j+\cos i\sin j$, so the matrix is $sc^T+cs^T$ with $s=(\sin i)_i$ and $c=(\cos i)_i$, and its rank is $\le2$. The $2\times2$ minor in rows and columns $1,2$ is $\sin2\sin4-\sin^23=\tfrac12(\cos2-\cos6)-\tfrac12(1-\cos6)=\tfrac12(\cos2-1)\ne0$. Rank $2$.
7 If $B=PA$ with $P$ invertible, $Ax=0\Rightarrow Bx=0$ and $Bx=0\Rightarrow Ax=P^{-1}Bx=0$. The column spaces need not agree: $\begin{pmatrix}1\\1\end{pmatrix}$ and $\begin{pmatrix}1\\0\end{pmatrix}$ are row equivalent, with column spaces $\operatorname{span}\{(1,1)\}\ne\operatorname{span}\{(1,0)\}$. (Their dimensions agree.)
8 The determinant is $1\cdot(1-0)-1\cdot(0-1)+0=2$. Over $\mathbb{R}$: rank $3$. Over $\mathbb{F}_2$: $2=0$ and $R_1+R_2=(1,0,1)=R_3$, while $R_1,R_2$ are independent: rank $2$.
II
Rank inequalities.
  • 1 Let $A\in M_{3\times5}(\mathbb{R})$ have rank $3$ and $B\in M_{5\times4}(\mathbb{R})$ rank $4$. Find all possible values of $\operatorname{rank}(AB)$, with examples.
  • 2 Prove that $A\in M_n(\mathbb{F})$ with $A^2=0$ has rank at most $n/2$, and give a $4\times4$ example of rank $2$.
  • 3 Prove $\operatorname{rank}(A^TA)=\operatorname{rank}A$ for every real $m\times n$ matrix, and deduce that $A^TA$ is invertible iff the columns of $A$ are independent.
  • 4 Prove that $\operatorname{rank}P+\operatorname{rank}(I-P)=n$ for every idempotent $P\in M_n(\mathbb{F})$, using only Sylvester's inequality and Theorem 8.34(3).
  • 5 Let $A\in M_n(\mathbb{F})$ with $A^3=0$. Prove $2\operatorname{rank}A^2\le\operatorname{rank}A$. If $n=5$ and $\operatorname{rank}A=3$, find $\operatorname{rank}A^2$.
  • 6 Prove that $\operatorname{rank}(AB)=\operatorname{rank}(BA)$ when $A,B\in M_n(\mathbb{F})$ and $A$ is invertible, and give $2\times2$ matrices for which the ranks differ.
  • 7 Give examples of $A,B\in M_2(\mathbb{R})$ of rank $1$ with $\operatorname{rank}(A+B)$ equal to $0$, $1$ and $2$.
1 Sylvester: $3+4-5=2\le\operatorname{rank}(AB)\le3$. Exactly: $\operatorname{rank}(AB)=4-\dim(C(B)\cap N(A))$ with $\dim N(A)=2$, $\dim C(B)=4$ in $\mathbb{R}^5$, so the intersection has dimension $1$ or $2$. Take $A=[I_3\ 0]$ (kernel $\operatorname{span}\{e_4,e_5\}$): $B=[e_1\ e_2\ e_3\ e_4]$ gives rank $3$; $B=[e_1\ e_2\ e_4\ e_5]$ gives rank $2$. Possible values: $\{2,3\}$.
2 $A\cdot A=0$ gives $2\operatorname{rank}A\le n$ (Theorem 8.36(1)). Example: $A=E_{13}+E_{24}$ ($e_3\mapsto e_1$, $e_4\mapsto e_2$, $e_1,e_2\mapsto0$), so $A^2e_j=0$ for all $j$ and $\operatorname{rank}A=2$.
3 Theorem 8.34(4): $A^TAx=0\Rightarrow\|Ax\|^2=x^TA^TAx=0\Rightarrow Ax=0$, so $N(A^TA)=N(A)$ and the ranks agree. $A^TA$ is $n\times n$, so it is invertible iff its rank is $n$ iff $\operatorname{rank}A=n$ iff the $n$ columns of $A$ are independent.
4 $P(I-P)=0$, so Sylvester gives $\operatorname{rank}P+\operatorname{rank}(I-P)-n\le0$. And $n=\operatorname{rank}I=\operatorname{rank}(P+(I-P))\le\operatorname{rank}P+\operatorname{rank}(I-P)$. Equality follows.
5 Frobenius with $(A,A,A)$: $\operatorname{rank}A^2+\operatorname{rank}A^2\le\operatorname{rank}A+\operatorname{rank}A^3=\operatorname{rank}A$. For $n=5$, $\operatorname{rank}A=3$: $\operatorname{rank}A^2\le1$, while Sylvester gives $\operatorname{rank}A^2\ge3+3-5=1$. So $\operatorname{rank}A^2=1$. (Such $A$ exists: $e_3\mapsto e_2\mapsto e_1\mapsto0$, $e_5\mapsto e_4\mapsto0$.)
6 $BA=A^{-1}(AB)A$, so Theorem 8.34(2) gives equal ranks. Example: $A=E_{12}$, $B=E_{11}$ give $AB=0$ and $BA=E_{12}$.
7 $B=-A$ (any rank-one $A$): rank $0$. $A=B=E_{11}$: $A+B=2E_{11}$, rank $1$. $A=E_{11}$, $B=E_{22}$: $A+B=I$, rank $2$.
III
Determinants, adjugates and Cramer's rule.
  • 1 Compute $\det\begin{pmatrix}2&0&1&3\\1&-1&0&2\\0&3&1&1\\4&1&2&0\end{pmatrix}$.
  • 2 Evaluate $\det\begin{pmatrix}1&1&1\\2&3&5\\4&9&25\end{pmatrix}$ without expanding.
  • 3 Let $D_n$ be the determinant of the $n\times n$ matrix with $2$ on the diagonal, $-1$ on the two adjacent diagonals and $0$ elsewhere. Prove $D_n=2D_{n-1}-D_{n-2}$ and find $D_n$.
  • 4 Let $A$ be real skew-symmetric. (a) Prove that $I+A$ is invertible. (b) Prove that $Q=(I-A)(I+A)^{-1}$ is orthogonal (the Cayley transform).
  • 5 Let $A\in M_3(\mathbb{R})$ with $\det A=-2$. Find $\det(3A)$, $\det(A^{-1})$, $\det(\operatorname{adj}A)$ and $\det(A^TA^2)$.
  • 6 Find $\operatorname{adj}A$ and $A^{-1}$ for $A=\begin{pmatrix}1&2&0\\0&1&3\\2&0&1\end{pmatrix}$.
  • 7 Solve $2x-y+z=3$, $x+y-z=0$, $x+2y+z=8$ by Cramer's rule.
  • 8 Using $\det(I_m+AB)=\det(I_n+BA)$, find $\det(I_n+uv^T)$ and the determinant of the $n\times n$ matrix with entries $a_{ij}=\delta_{ij}+ij$.
  • 9 Let $A\in M_n(\mathbb{Z})$ be invertible over $\mathbb{Q}$. Prove that $A^{-1}$ has integer entries iff $\det A=\pm1$.
Check: exact RREF, rank and determinant of any matrix you type
size—
rank—
det (square only)—
pivot columns—
Rows on separate lines; entries separated by spaces or commas; fractions like 3/4 and decimals are allowed.
1 $R_1\leftrightarrow R_2$ (the sign changes) puts the row $(1,-1,0,2)$ on top; then $R_2-2R_1$ and $R_4-4R_1$ give the rows $(0,2,1,-1)$, $(0,3,1,1)$, $(0,5,2,-8)$ below it. Expanding along column 1, $$\det A=-\det\begin{pmatrix}2&1&-1\\3&1&1\\5&2&-8\end{pmatrix}.$$ The $3\times3$ determinant is $2(-8-2)-1(-24-5)+(-1)(6-5)=-20+29-1=8$, so $\det A=-8$. (Confirm with the check-lab above.)
2 It is the transpose of the Vandermonde matrix of $2,3,5$ (columns $(1,x,x^2)^T$): $\det=(3-2)(5-2)(5-3)=6$.
3 Expand along row $1$: $D_n=2C_{11}+(-1)C_{12}$ with $C_{11}=D_{n-1}$. Deleting row 1 and column 2 leaves a matrix whose first column is $(-1,0,\dots,0)^T$ and whose lower-right block is the $(n-2)\times(n-2)$ matrix of the same type, so $M_{12}=-D_{n-2}$ and $C_{12}=(-1)^{1+2}M_{12}=D_{n-2}$. Hence $D_n=2D_{n-1}-D_{n-2}$. With $D_1=2$, $D_2=3$, the differences $D_n-D_{n-1}$ are constant $=1$, so $D_n=n+1$.
4 (a) If $(I+A)x=0$, then $0=x^T(I+A)x=\|x\|^2+x^TAx$, and $x^TAx=(x^TAx)^T=x^TA^Tx=-x^TAx$ gives $x^TAx=0$; so $x=0$. (b) $(I+A)^T=I-A$ and $(I-A)^T=I+A$, and $I-A$, $I+A$ commute. So $Q^TQ=(I-A)^{-1}(I+A)(I-A)(I+A)^{-1}=(I-A)^{-1}(I-A)(I+A)(I+A)^{-1}=I$. ($I-A$ is invertible by (a) applied to $-A$.)
5 $\det(3A)=3^3(-2)=-54$; $\det A^{-1}=-\tfrac12$; $\det\operatorname{adj}A=(-2)^2=4$; $\det(A^TA^2)=\det A\cdot(\det A)^2=-8$.
6 $\det A=1(1-0)-2(0-6)+0=13$. Cofactors: $C_{11}=1$, $C_{12}=6$, $C_{13}=-2$, $C_{21}=-2$, $C_{22}=1$, $C_{23}=4$, $C_{31}=6$, $C_{32}=-3$, $C_{33}=1$. Transposing, $\operatorname{adj}A=\begin{pmatrix}1&-2&6\\6&1&-3\\-2&4&1\end{pmatrix}$ and $A^{-1}=\tfrac1{13}\operatorname{adj}A$. Check: row 1 of $A$ times column 1 of $\operatorname{adj}A$: $1+12+0=13$. ✓
7 $\det A=2(1+2)+1(1+1)+1(2-1)=9$; $\det A_1=9$, $\det A_2=18$, $\det A_3=27$. So $(x,y,z)=(1,2,3)$. Check: $2-2+3=3$, $1+2-3=0$, $1+4+3=8$. ✓
8 With $A=u$, $B=v^T$: $\det(I_n+uv^T)=1+v^Tu$. The matrix $\delta_{ij}+ij$ is $I+ww^T$ with $w=(1,\dots,n)^T$, so its determinant is $1+\sum_{k=1}^nk^2=1+\tfrac{n(n+1)(2n+1)}6$.
9 If $A^{-1}\in M_n(\mathbb{Z})$, then $\det A$ and $\det A^{-1}$ are integers with product $1$, so $\det A=\pm1$. Conversely $\operatorname{adj}A$ has integer entries (cofactors are integer determinants), and $A^{-1}=\pm\operatorname{adj}A$.
IV
Linear systems and special matrices.
  • 1 Discuss, for all real $a,b$, the system $x+y+2z=1$, $2x+3y+5z=4$, $x+2y+az=b$, and solve it whenever it is consistent.
  • 2 A consistent system of linear equations over $\mathbb{F}_3$ has $5$ unknowns and a coefficient matrix of rank $2$. How many solutions does it have?
  • 3 For which real $k$ does $x+ky=1$, $kx+y=1$ have a unique solution, no solution, infinitely many solutions?
  • 4 Prove that the solution set of $Ax=b$ is a subspace of $\mathbb{F}^n$ if and only if $b=0$.
  • 5 Prove that a real upper triangular orthogonal matrix is diagonal with diagonal entries $\pm1$.
  • 6 Let $N=\begin{pmatrix}0&1&2\\0&0&3\\0&0&0\end{pmatrix}$. Find $(I-N)^{-1}$ and $\det(I+5N)$.
  • 7 Prove that the only real $2\times2$ matrices that are both orthogonal and symmetric are $\pm I$ and the reflections $\begin{pmatrix}\cos\theta&\sin\theta\\\sin\theta&-\cos\theta\end{pmatrix}$.
  • 8 (Modelling) Balance the combustion of propane, $a\,\mathrm{C_3H_8}+b\,\mathrm{O_2}\to c\,\mathrm{CO_2}+d\,\mathrm{H_2O}$, by setting up a homogeneous system for $(a,b,c,d)$ and finding its null space.
1 $R_2-2R_1=(0,1,1\mid2)$, $R_3-R_1=(0,1,a-2\mid b-1)$, then $R_3-R_2=(0,0,a-3\mid b-3)$; $\det A=a-3$. If $a\ne3$: $z=\tfrac{b-3}{a-3}$, $y=2-z$, $x=1-y-2z=-1-z$. If $a=3$, $b\ne3$: no solution. If $a=3$, $b=3$: $(x,y,z)=(-1,2,0)+t(-1,-1,1)$.
2 The solution set is $x_0+N(A)$ with $\dim N(A)=5-2=3$, so it has $3^3=27$ elements.
3 $\det A=1-k^2$. If $k\ne\pm1$: unique solution $x=y=\tfrac1{1+k}$. If $k=1$ both equations are $x+y=1$: infinitely many. If $k=-1$: $x-y=1$ and $-x+y=1$ add to $0=2$: no solution.
4 If $b=0$ the solution set is $N(A)$, a subspace. If it is a subspace it contains $0$, so $b=A0=0$.
5 $Q^{-1}$ is upper triangular (Theorem 8.47(b)) and equals $Q^T$, which is lower triangular. So $Q^T$ is diagonal, hence so is $Q$; a diagonal $Q$ with $Q^TQ=I$ has $q_{ii}^2=1$.
6 $N^2=\begin{pmatrix}0&0&3\\0&0&0\\0&0&0\end{pmatrix}$, $N^3=0$, so $(I-N)^{-1}=I+N+N^2=\begin{pmatrix}1&1&5\\0&1&3\\0&0&1\end{pmatrix}$. $\det(I+5N)=1$ (unitriangular). Check: $(I-N)$ times this matrix: first row $(1,-1,-2)$ gives $(1,\ 1-1,\ 5-3-2)=(1,0,0)$. ✓
7 By Theorem 8.50 an orthogonal $2\times2$ matrix is a rotation or a reflection. Reflections are symmetric. A rotation is symmetric iff $\sin\theta=-\sin\theta$, i.e. $\sin\theta=0$, giving $\pm I$.
8 Atom counts: C: $3a=c$; H: $8a=2d$; O: $2b=2c+d$. The coefficient matrix (unknowns $a,b,c,d$) has rank $3$, so the null space is a line: $c=3a$, $d=4a$, $b=\tfrac{2c+d}2=5a$. Smallest positive integers: $\mathrm{C_3H_8}+5\,\mathrm{O_2}\to3\,\mathrm{CO_2}+4\,\mathrm{H_2O}$.
🎯 Exam corner CSIR Part BCSIR Part CGATE MA

E1. CSIR Part B GATE MA Let $A$ be a real $4\times6$ matrix of rank $4$ and $B$ a real $6\times5$ matrix of rank $4$. Which of the following cannot be the rank of $AB$? (A) $1$; (B) $2$; (C) $3$; (D) $4$.

Idea $\operatorname{rank}(AB)=\operatorname{rank}B-\dim(C(B)\cap N(A))$, with $\dim N(A)=2$.
Range The intersection has dimension $0$, $1$ or $2$ (all occur: with $A=[I_4\ 0]$, $N(A)=\operatorname{span}\{e_5,e_6\}$, and $C(B)$ can be spanned by $e_1,\dots,e_4$, or $e_1,e_2,e_3,e_5$, or $e_1,e_2,e_5,e_6$). So $\operatorname{rank}(AB)\in\{2,3,4\}$, in agreement with Sylvester's bound $4+4-6=2$.
Answer (A).

E2. CSIR Part B The determinant of the $5\times5$ real matrix with every diagonal entry $3$ and every off-diagonal entry $-1$ is (A) $-256$; (B) $256$; (C) $0$; (D) $-64$.

Idea The matrix is $4I-J$ ($J$ all ones), i.e. $aI+bJ$ with $a=4$, $b=-1$.
Compute $\det=a^{n-1}(a+nb)=4^4(4-5)=-256$ (Example 4(b)). Sanity check: $(4I-J)\mathbf 1=4\cdot\mathbf 1-5\cdot\mathbf 1=-\mathbf 1$, while every vector with coordinate sum $0$ is multiplied by $4$; a $4$-dimensional space stretched by $4$ and one direction reversed give $4^4\cdot(-1)$.
Answer (A).

E3. CSIR Part B Let $A$ be a real $4\times4$ matrix with $\det A=3$. Then $\det\big(\operatorname{adj}(2A)\big)$ equals (A) $2^{12}\cdot3^3$; (B) $2^4\cdot3^3$; (C) $2^{12}\cdot3^4$; (D) $2^3\cdot3^3$.

Idea $\operatorname{adj}(cA)=c^{n-1}\operatorname{adj}A$ and $\det(\operatorname{adj}A)=(\det A)^{n-1}$.
Compute $\operatorname{adj}(2A)=2^3\operatorname{adj}A$, so $\det\operatorname{adj}(2A)=(2^3)^4\det\operatorname{adj}A=2^{12}\cdot3^3=110592$. Equivalently $\det\operatorname{adj}(2A)=(\det 2A)^3=(2^4\cdot3)^3$.
Answer (A).

E4. CSIR Part C Let $A,B\in M_n(\mathbb{R})$, $n\ge2$. Which of the following statements are always true? (One or more options may be correct.) (A) $\operatorname{rank}(AB)=\operatorname{rank}(BA)$; (B) $\operatorname{rank}(A^TA)=\operatorname{rank}A$; (C) if $A^2=0$ then $\operatorname{rank}A\le n/2$; (D) $\operatorname{rank}(A+B)\ge\operatorname{rank}A+\operatorname{rank}B-n$.

(A) False $A=E_{12}$, $B=E_{11}$ (padded with zeros to size $n$): $\operatorname{rank}AB=0$, $\operatorname{rank}BA=1$.
(B) True $N(A^TA)=N(A)$ over $\mathbb{R}$ (Theorem 8.34(4)).
(C) True $AA=0$ gives $2\operatorname{rank}A\le n$ (Theorem 8.36(2)).
(D) False $A=I$, $B=-I$: $0\ge n+n-n=n$ fails. (The inequality is Sylvester's for products, not sums.)
Answer (B) and (C).

E5. CSIR Part C Let $A\in M_3(\mathbb{R})$ satisfy $A^2=A$, $A\ne0$, $A\ne I$. Which of the following are true? (A) $\det A=0$; (B) $\operatorname{tr}A\in\{1,2\}$; (C) $A$ is symmetric; (D) $I-2A$ is invertible.

(A) True An invertible idempotent is $I$ (multiply $A^2=A$ by $A^{-1}$); $A\ne I$, so $A$ is singular.
(B) True $\operatorname{tr}A=\operatorname{rank}A$ (Theorem 8.49(3), characteristic $0$), and $\operatorname{rank}A\ne0,3$ because $A\ne0$ and $A\ne I$.
(C) False $A=\begin{pmatrix}1&1&0\\0&0&0\\0&0&0\end{pmatrix}$ satisfies $A^2=A$ and is not symmetric: idempotents are projections, not necessarily orthogonal ones.
(D) True $(I-2A)^2=I-4A+4A^2=I$, so $I-2A$ is its own inverse.
Answer (A), (B) and (D).

E6. CSIR Part C GATE MA Let $A$ be a real $5\times3$ matrix of rank $3$. Which of the following are true? (A) For every $b\in\mathbb{R}^5$ the system $Ax=b$ has at most one solution; (B) $AA^T$ is invertible; (C) $A^TA$ is invertible; (D) there is a $3\times5$ matrix $C$ with $AC=I_5$.

(A) True $\dim N(A)=3-3=0$, so a consistent system has a unique solution (Theorem 8.44(3)); for $b\notin C(A)$ it has none.
(B) False $AA^T$ is $5\times5$ of rank $\operatorname{rank}A=3\lt5$.
(C) True $A^TA$ is $3\times3$ of rank $3$ (Theorem 8.34(4)).
(D) False $\operatorname{rank}(AC)\le\operatorname{rank}A=3\lt5$. (A left inverse exists: $C=(A^TA)^{-1}A^T$ gives $CA=I_3$.)
Answer (A) and (C).
🧑‍🏫 For the teacher

Suggested plan — 3 lectures × 60 min.

  1. Elimination and rank. Elementary matrices (Theorem 8.30), the RREF and the "column relations are preserved" observation that proves its uniqueness (Theorem 8.31). Do Example 1 on the board, then project Interactive 1 in the Example 1 mode and pause at each pivot to ask "free or pivot column?". Theorem 8.32 (row rank = column rank) and the rank normal form. End with Example 2 and the separable-entries trick.
  2. Rank inequalities and determinants. Formula $(\ast)$ and Frobenius ⇒ Sylvester (Theorem 8.35) with a picture of $C(B)\cap N(A)$; Theorem 8.36 and Example 3. Determinant axioms (Theorem 8.37), the product rule via elementary matrices, Laplace expansion. Interactive 1 in the square mode shows the determinant factor changing only at swaps and scalings — let students predict $\det$ at $t=-3$ before the end.
  3. Adjugates, systems, special matrices. Theorem 8.42 and Example 5 (rank of the adjugate is a favourite exam question), Rouché–Capelli and Cramer with Interactive 2 (sweep through $t=\tfrac12$; then set $s=2$). Example 6 live. Finish with Theorems 8.48–8.50 and Example 7, and Exam-corner E4–E5.

Discussion questions. (1) Why does the proof that the RREF is unique need nothing but the fact that row operations preserve $N(A)$? (2) The determinant is defined by a sum of $n!$ terms, yet it is computed in about $n^3$ operations — where exactly does the saving come from? (3) In Interactive 2, why does the intersection point run away to infinity as $\det A\to0$ instead of simply disappearing? What does this say about solving nearly singular systems on a computer?

Misconceptions to watch for. Taking the pivot columns of the RREF as a basis of $C(A)$; believing $\operatorname{rank}(AB)=\operatorname{rank}(BA)$; writing $\det(cA)=c\det A$ or $\det(A+B)=\det A+\det B$; concluding "infinitely many solutions" from $\det A=\det A_i=0$; using $\operatorname{rank}(A^TA)=\operatorname{rank}A$ over $\mathbb{C}$; thinking idempotents must be symmetric; "trace = rank" for idempotents over $\mathbb{F}_2$.

Suggested homework. I(1, 2, 4, 6, 8), II(1, 2, 5, 6), III(2, 3, 5, 6, 8), IV(1, 2, 5, 6, 8); Exam corner E1, E3, E6.

🔬 Research–Teaching NexusResearch-tutored · optional, about 60 minutes

Research question. If the entries of an $n\times n$ matrix are chosen at random, how likely is the matrix to be invertible — over a finite field, and for random $\pm1$ entries over $\mathbb{R}$?

Why it matters. In random linear network coding, used in research on satellite and wireless broadcasting and in distributed cloud storage, a receiver collects random linear combinations of data packets over a finite field such as $\mathbb{F}_{256}$ and recovers the data by solving a linear system — which works exactly when the random coefficient matrix is invertible. Random $\pm1$ matrices model the measurement matrices of compressed sensing (used in medical MRI acceleration) and their singularity probability was a famous open problem until 2020.

What to do.

  1. Count, by the argument of §8.1 (choose columns one at a time, each outside the span of the previous ones), the invertible $n\times n$ matrices over $\mathbb{F}_q$, and show that the probability of invertibility is $\prod_{k=1}^n(1-q^{-k})$.
  2. Tabulate this for $q=2,3,256$ and $n=1,\dots,10$, and compute the limits as $n\to\infty$. Why does the probability not tend to $0$ even though larger matrices have more "chances" to be singular?
  3. Verify your formula for $q=2$, $n=3$ by brute force (enumerate all $512$ matrices) or by simulation with Gaussian elimination mod $2$.
  4. For random $\pm1$ matrices over $\mathbb{R}$, find the singularity probability exactly for $n=2,3,4$ by enumeration, and estimate it by simulation for $n=5,\dots,12$ (use exact integer elimination or a rank test with care).

Tools: Python (NumPy, or plain integers with arithmetic mod $q$), or any language with exact integer arithmetic; the mini check-lab above for spot checks.

Hand in: A one-page report with the formula and its proof, the two tables, and a plot of the $\pm1$ singularity probability against $n$ on a logarithmic scale.

Going further. Read about the theorem of K. Tikhomirov (2020) that a random $n\times n$ $\pm1$ matrix is singular with probability $\big(\tfrac12+o(1)\big)^n$, and explain why $\left(\tfrac12\right)^n$-type events (two equal or opposite rows) make this the natural answer.

Instructor note: over $\mathbb{F}_2$ the probabilities are $\tfrac12,\tfrac38,\tfrac{21}{64},\tfrac{315}{1024}\approx0.3076,\dots$ with limit $\approx0.2888$; over $\mathbb{F}_3$ the limit is $\approx0.5601$; over $\mathbb{F}_{256}$ it is $\approx0.9961$ — the reason network coding uses byte-sized fields. For $\pm1$ matrices the exact singularity probabilities are $\tfrac12$, $\tfrac58$, $\tfrac{169}{256}\approx0.660$ for $n=2,3,4$; simulation gives about $0.66$ at $n=5$, $0.52$ at $n=8$ and $0.37$ at $n=10$, so the decay only becomes visible for moderate $n$. Note that the determinant of a $\pm1$ matrix is always a multiple of $2^{n-1}$, which makes a floating-point zero test safe for small $n$.

🧪 Self-check quiz

0/5 correct

Q1. For $n\ge2$, the rank of the $n\times n$ matrix with entries $a_{ij}=i+j$ is

Q2. If $A\in M_3(\mathbb{R})$ and $\det A=5$, then $\det(2A)$ is

Q3. Let $A$ be a real $3\times3$ matrix of rank $2$ and $b\in\mathbb{R}^3$. The system $Ax=b$

Q4. Which of these real $n\times n$ matrices is necessarily singular?

Q5. $A$ is a real $3\times4$ matrix of rank $3$ and $B$ a real $4\times3$ matrix of rank $3$. The smallest possible rank of $AB$ is