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
The three elementary row operations on a matrix are:
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.
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$. ∎
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.
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. ∎
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)$.
Let $A\in M_{m\times n}(\mathbb{F})$ and let $R=\operatorname{rref}(A)$ have $r$ pivots. Then:
- the nonzero rows of $R$ form a basis of the row space of $A$;
- the pivot columns of $A$ (not of $R$) form a basis of $C(A)$;
- 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)$;
- (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}$. ∎
Let $A\in M_{m\times n}(\mathbb{F})$ have rank $r$. Then:
- 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;
- $A=BC$ with $B\in M_{m\times r}$, $C\in M_{r\times n}$, both of rank $r$ (a rank factorisation);
- $\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$). ∎
- 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.
- 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.
- 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.
- 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).
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.
Let $A\in M_{m\times n}(\mathbb{F})$ and let $B$ be of the size required in each statement.
- $\operatorname{rank}(AB)\le\min(\operatorname{rank}A,\operatorname{rank}B)$ for $B\in M_{n\times p}(\mathbb{F})$.
- $\operatorname{rank}(PAQ)=\operatorname{rank}A$ for invertible $P\in M_m(\mathbb{F})$, $Q\in M_n(\mathbb{F})$.
- $\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})$.
- 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)$$(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). ∎
- 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$.
- If $A\in M_n(\mathbb{F})$ and $A^2=0$, then $\operatorname{rank}A\le n/2$.
- 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$. ∎
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).
Regard $\det$ as a function of the rows $r_1,\dots,r_n$ of $A$. Then:
- (multilinear) $\det$ is linear in each row when the other rows are fixed;
- (alternating) if two rows of $A$ are equal, $\det A=0$;
- (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. ∎
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$. ∎
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$. ∎
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)$.)
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$. ∎
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. ∎
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:
- $\det(\operatorname{adj}A)=(\det A)^{n-1}$ and $\operatorname{adj}(cA)=c^{n-1}\operatorname{adj}A$;
- $\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$;
- $\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$. ∎
(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)$. ∎
Linear Systems: Rouché–Capelli and Cramer's Rule
Let $A\in M_{m\times n}(\mathbb{F})$, $b\in\mathbb{F}^m$ and $r=\operatorname{rank}A$.
- $Ax=b$ is consistent if and only if $\operatorname{rank}A=\operatorname{rank}[A\mid b]$, i.e. iff $b\in C(A)$.
- 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.
- 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$.
- 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$.
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.
For $A\in M_n(\mathbb{F})$ the following are equivalent:
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. ∎
- Row-reduce the augmented matrix without dividing by expressions that might vanish (use replacements and swaps; postpone scaling).
- 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.
- 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).
Special Matrices
A matrix $A\in M_n(\mathbb{F})$ is
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$. ∎
Let $N\in M_n(\mathbb{F})$ be nilpotent of index $k$. Then:
- $k\le n$, i.e. $N^n=0$;
- $N$ is similar to a strictly upper triangular matrix;
- $\det N=0$, $\operatorname{tr}N=0$ and $\det(I+cN)=1$ for every scalar $c$;
- $I-N$ is invertible, with $(I-N)^{-1}=I+N+N^2+\cdots+N^{k-1}$;
- 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$. ∎
Let $P\in M_n(\mathbb{F})$ with $P^2=P$ and $r=\operatorname{rank}P$. Then:
- $I-P$ is idempotent, $P(I-P)=(I-P)P=0$, and $N(P)=C(I-P)$;
- $\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)$;
- $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$;
- $\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.) ∎
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$. ∎
- $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.
- 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.
- $\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$.
- 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}$.
- 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$.
- 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).
- 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.
- 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$.
- "Trace equals rank" for idempotents needs characteristic $0$. Over $\mathbb{F}_2$, $I_2$ is idempotent of rank $2$ and trace $0$.
- Odd skew-symmetric matrices are singular — except in characteristic $2$. Over $\mathbb{F}_2$, $(1)$ is skew-symmetric and invertible.
- $\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$).
- 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
- 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 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 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$.
- 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.
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$.
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$.
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$.
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$.
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.
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$.
Suggested plan — 3 lectures × 60 min.
- 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.
- 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.
- 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 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.
- 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})$.
- 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?
- Verify your formula for $q=2$, $n=3$ by brute force (enumerate all $512$ matrices) or by simulation with Gaussian elimination mod $2$.
- 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.
🧪 Self-check quiz
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