Formula & theorem reference

(\implies) If W is a subspace, it is itself a vector space under the addition and scalar multiplication inherited from V, so both closure properties hold automatically — that direction is immediate from the definition of "subspace" and needs no further argument.

(\impliedby) This is the direction that does real work: assume W is nonempty and closed under addition and scalar multiplication, and check that W inherits every vector space axiom from V.

First, \mathbf{0} \in W. Since W is nonempty, pick any \mathbf{u} \in W. Closure under scalar multiplication with c = 0 gives 0 \cdot \mathbf{u} = \mathbf{0} \in W. So W contains the zero vector without that having to be assumed separately — it falls out of nonemptiness plus scalar closure.

Next, every \mathbf{u} \in W has its negative in W: closure under scalar multiplication with c = -1 gives (-1)\mathbf{u} = -\mathbf{u} \in W.

With \mathbf{0} \in W and negatives available inside W, the two closure hypotheses supply exactly the operations W needs: addition of any two elements of W stays in W, and scaling any element of W by any real number stays in W. So W is closed under both vector space operations, and it contains an additive identity and additive inverses drawn from that same closure.

Every remaining axiom — commutativity and associativity of addition, associativity of scalar multiplication, the distributive laws, and the identity 1 \cdot \mathbf{u} = \mathbf{u} — is an equation that holds for all vectors in V, by hypothesis that V is a vector space. Since every element of W is in particular an element of V, each of these equations holds for the elements of W too; W is not required to satisfy some different, weaker set of axioms, only the same ones V already satisfies for every vector it contains. So none of these need separate verification — they are inherited, not re-derived.

Having the two closure properties, an identity element, inverses, and every other axiom inherited for free, W satisfies the full definition of a vector space under the operations of V, restricted to W. That makes W a subspace of V.

Why the test stops at two conditions. A first guess might list three requirements — closure under addition, closure under scalar multiplication, and \mathbf{0} \in W — and that three-condition version is also correct and commonly used. The proof above shows why the third condition is redundant whenever W is already known to be nonempty: scaling any single element of W by 0 produces \mathbf{0}, so nonemptiness plus scalar closure already forces \mathbf{0} \in W. The nonemptiness hypothesis cannot be dropped, though — \varnothing satisfies both closure conditions vacuously (there are no pairs or elements to violate them) but is not a vector space, since it has no zero vector.

Sanity check: take V = \mathbb{R}^2 and W = \{(x, y) : y = x\}, the line through the origin. Adding two points on that line, (a, a) + (b, b) = (a+b, a+b), lands back on the line, and scaling, c(a,a) = (ca, ca), does too — both closure conditions hold, so the test confirms W is a subspace, matching the geometric fact that a line through the origin is a subspace of the plane. Shift the line off the origin to W' = \{(x, y) : y = x + 1\} and closure under scalar multiplication already fails: (0,1) \in W' but 2(0,1) = (0,2) \notin W', correctly flagging that a line missing the origin is not a subspace.

First claim. Suppose \mathbf{v}_k is a linear combination of the other vectors in S, say \mathbf{v}_k = c_1\mathbf{v}_1 + \cdots + c_{k-1}\mathbf{v}_{k-1} + c_{k+1}\mathbf{v}_{k+1} + \cdots + c_p\mathbf{v}_p. Write S' = S \setminus \{\mathbf{v}_k\}. Since S' \subseteq S, every vector reachable as a combination of S' is automatically reachable as a combination of S, so \operatorname{span}(S') \subseteq H.

For the reverse inclusion, take any \mathbf{y} \in H. Then \mathbf{y} is some combination \mathbf{y} = a_1\mathbf{v}_1 + \cdots + a_k\mathbf{v}_k + \cdots + a_p\mathbf{v}_p. Substitute the expression for \mathbf{v}_k above in place of \mathbf{v}_k and collect terms: each \mathbf{v}_i with i \neq k now carries the combined coefficient a_i + a_k c_i, and \mathbf{v}_k has vanished entirely. So \mathbf{y} is a linear combination of S' alone, giving H \subseteq \operatorname{span}(S'). The two inclusions together give \operatorname{span}(S') = H.

Second claim. If H \neq \{\mathbf{0}\}, then S contains at least one nonzero vector, so among all subsets of S that span H, choose one, call it B, with the fewest vectors possible (such a subset exists because S itself spans H and S is finite, so there are only finitely many subsets to compare). It remains to show B is linearly independent, which makes it a basis for H.

Suppose toward a contradiction that B is linearly dependent. Then some vector in B is a linear combination of the others in B — removing that vector, by the first claim applied to B in place of S, leaves a smaller subset of B (hence of S) that still spans H. This contradicts the minimality of B. So B is linearly independent, and since B already spans H, B is a basis for H.

Sanity check: with S = \{\mathbf{v}_1, \mathbf{v}_2\} where \mathbf{v}_2 = 3\mathbf{v}_1 and \mathbf{v}_1 \neq \mathbf{0}, the second vector is a multiple of the first, so dropping it leaves S' = \{\mathbf{v}_1\} with \operatorname{span}(S') = \operatorname{span}(S) exactly as the theorem predicts — and \{\mathbf{v}_1\} is itself the minimal, linearly independent spanning set, i.e. the basis the second claim guarantees.

Write S = \{v_1, \dots, v_n\}. Two facts about V are already on hand from the definition of dimension: every linearly independent subset of V can be grown, one vector at a time, into a basis of V; and every basis of V has exactly n vectors, since \dim V = n.

Independent \implies spanning. Suppose S is linearly independent but, toward a contradiction, does not span V. Then some w \in V lies outside \operatorname{span}(S). Adjoining w to S keeps the set independent: if c_1v_1 + \cdots + c_nv_n + c_{n+1}w = 0 with c_{n+1} \ne 0, solving for w would express it as a combination of v_1,\dots,v_n, placing w in \operatorname{span}(S) — which was excluded — so c_{n+1} = 0, and then the independence of S forces every remaining c_i = 0 as well. So S \cup \{w\} is an independent set of n+1 vectors. Extend it to a basis of V exactly as in the growing process above; that basis has at least n+1 vectors, contradicting \dim V = n. No such w exists, so S spans V, and an independent spanning set is by definition a basis.

Spanning \implies independent. Suppose S spans V but, toward a contradiction, is linearly dependent. Dependence means some v_k is a linear combination of the other n-1 vectors in S; deleting v_k leaves a set of n-1 vectors whose span is unchanged, since every occurrence of v_k in a combination can be rewritten using the rest. So V is spanned by only n - 1 vectors. A basis can always be extracted from a spanning set by discarding vectors that are combinations of the others already kept, so V would have a basis of at most n-1 vectors — contradicting \dim V = n. No such dependence exists, so S is independent, and again an independent spanning set is a basis.

Sanity check: in \mathbb{R}^2, where n = 2, the two vectors (1,1) and (1,-1) are independent (neither is a scalar multiple of the other), so the theorem guarantees — without any separate spanning check — that they already span all of \mathbb{R}^2.

Let k = \dim\left(\operatorname{Nul}A\right) and pick a basis \{\mathbf{v}_1,\dots,\mathbf{v}_k\} for \operatorname{Nul}A, the set of vectors in \mathbb{R}^n that A sends to \mathbf{0}. Since any basis for a subspace of \mathbb{R}^n extends to a basis of the whole space, choose vectors \mathbf{v}_{k+1},\dots,\mathbf{v}_n so that \{\mathbf{v}_1,\dots,\mathbf{v}_n\} is a basis for \mathbb{R}^n. The claim is that the n-k image vectors A\mathbf{v}_{k+1},\dots,A\mathbf{v}_n form a basis for \operatorname{Col}A, which pins \operatorname{rank}(A) = n-k and finishes the proof.

Spanning. Every \mathbf{b}\in\operatorname{Col}A has the form A\mathbf{x} for some \mathbf{x}\in\mathbb{R}^n. Write \mathbf{x} in the extended basis as \mathbf{x} = c_1\mathbf{v}_1 + \cdots + c_n\mathbf{v}_n. Applying A and using linearity, \mathbf{b} = A\mathbf{x} = c_1A\mathbf{v}_1 + \cdots + c_kA\mathbf{v}_k + c_{k+1}A\mathbf{v}_{k+1} + \cdots + c_nA\mathbf{v}_n. The first k terms vanish because \mathbf{v}_1,\dots,\mathbf{v}_k \in \operatorname{Nul}A, leaving \mathbf{b} = c_{k+1}A\mathbf{v}_{k+1} + \cdots + c_nA\mathbf{v}_n. So the n-k image vectors already span \operatorname{Col}A.

Independence. Suppose c_{k+1}A\mathbf{v}_{k+1} + \cdots + c_nA\mathbf{v}_n = \mathbf{0}. By linearity this is A(c_{k+1}\mathbf{v}_{k+1} + \cdots + c_n\mathbf{v}_n) = \mathbf{0}, which puts the vector \mathbf{w} = c_{k+1}\mathbf{v}_{k+1} + \cdots + c_n\mathbf{v}_n inside \operatorname{Nul}A. Since \{\mathbf{v}_1,\dots,\mathbf{v}_k\} is a basis for \operatorname{Nul}A, \mathbf{w} also equals some combination d_1\mathbf{v}_1 + \cdots + d_k\mathbf{v}_k. Subtracting the two expressions for \mathbf{w} gives d_1\mathbf{v}_1 + \cdots + d_k\mathbf{v}_k - c_{k+1}\mathbf{v}_{k+1} - \cdots - c_n\mathbf{v}_n = \mathbf{0}, a linear relation among all n vectors of the basis \{\mathbf{v}_1,\dots,\mathbf{v}_n\}. Basis vectors are linearly independent, so every coefficient here is 0 — in particular c_{k+1} = \cdots = c_n = 0. Only the trivial combination of A\mathbf{v}_{k+1},\dots,A\mathbf{v}_n gives \mathbf{0}, so these vectors are linearly independent.

Together, spanning and independence make \{A\mathbf{v}_{k+1},\dots, A\mathbf{v}_n\} a basis for \operatorname{Col}A, so \operatorname{rank}(A) = \dim\left(\operatorname{Col}A\right) = n-k. Moving k to the other side recovers \operatorname{rank}(A) + \dim\left(\operatorname{Nul}A\right) = n.

Sanity check: for the 3\times 3 identity matrix, \operatorname{Nul}A = \{\mathbf{0}\}, so k = 0 and \operatorname{rank}(A) = 3 = n, matching the fact that the identity is invertible and its columns already span \mathbb{R}^3. At the other extreme, the 3\times 3 zero matrix has \operatorname{Nul}A = \mathbb{R}^3, so k=3 and \operatorname{rank}(A) = 0 — no columns to span anything — and 0 + 3 = 3 still checks out.

To show \ker T is a subspace of V, three things must hold: it contains the zero vector, it is closed under addition, and it is closed under scalar multiplication.

Contains the zero vector. Linearity forces T(\mathbf{0}) = \mathbf{0}: writing \mathbf{0} = 0\mathbf{v} for any \mathbf{v} \in V, T(\mathbf{0}) = T(0\mathbf{v}) = 0\, T(\mathbf{v}) = \mathbf{0}. So \mathbf{0} \in \ker T, and \ker T is nonempty.

Closed under addition. Let \mathbf{u}, \mathbf{v} \in \ker T, so T(\mathbf{u}) = \mathbf{0} and T(\mathbf{v}) = \mathbf{0}. Then T(\mathbf{u} + \mathbf{v}) = T(\mathbf{u}) + T(\mathbf{v}) = \mathbf{0} + \mathbf{0} = \mathbf{0}, using additivity of T. Hence \mathbf{u} + \mathbf{v} \in \ker T.

Closed under scalar multiplication. Let \mathbf{v} \in \ker T and let c be any scalar. Then T(c\mathbf{v}) = c\, T(\mathbf{v}) = c\mathbf{0} = \mathbf{0}, using homogeneity of T. Hence c\mathbf{v} \in \ker T.

All three closure properties hold, so \ker T is a subspace of V.

Sanity check: if T is the zero transformation, T(\mathbf{v}) = \mathbf{0} for every \mathbf{v} \in V, so \ker T = V itself — the whole space, which is certainly a subspace of V. At the other extreme, if T is one-to-one, the only vector sent to \mathbf{0} is \mathbf{0} itself, so \ker T = \{\mathbf{0}\}, the trivial subspace. Both extremes are genuine subspaces, exactly as the theorem guarantees.

Every \mathbf{x} \in V has a unique expansion in the \mathcal{B}-basis, \mathbf{x} = x_1\mathbf{b}_1 + x_2\mathbf{b}_2 + \cdots + x_n\mathbf{b}_n, where the scalars x_1, \dots, x_n are exactly the entries of [\mathbf{x}]_{\mathcal B}. Take \mathcal{C}-coordinates of both sides. Coordinate-taking relative to a fixed basis is linear — the coordinate map sends sums to sums and scalar multiples to scalar multiples, since it just reads off the unique coefficients in a linear combination — so [\mathbf{x}]_{\mathcal C} = [x_1\mathbf{b}_1 + \cdots + x_n\mathbf{b}_n]_{\mathcal C} = x_1[\mathbf{b}_1]_{\mathcal C} + x_2[\mathbf{b}_2]_{\mathcal C} + \cdots + x_n[\mathbf{b}_n]_{\mathcal C}. The right side is precisely a linear combination of the columns of P_{\mathcal C \leftarrow \mathcal B} with weights x_1, \dots, x_n, which is the definition of the matrix-vector product: x_1[\mathbf{b}_1]_{\mathcal C} + \cdots + x_n[\mathbf{b}_n]_{\mathcal C} = \begin{bmatrix} [\mathbf{b}_1]_{\mathcal C} & \cdots & [\mathbf{b}_n]_{\mathcal C} \end{bmatrix}\begin{bmatrix} x_1 \\ \vdots \\ x_n \end{bmatrix} = P_{\mathcal C \leftarrow \mathcal B}\,[\mathbf{x}]_{\mathcal B}. Combining the two displays gives [\mathbf{x}]_{\mathcal C} = P_{\mathcal C \leftarrow \mathcal B}\,[\mathbf{x}]_{\mathcal B}, as claimed.

For invertibility, run the same argument with the roles of \mathcal{B} and \mathcal{C} swapped: the matrix P_{\mathcal B \leftarrow \mathcal C} built from the \mathcal{B}-coordinates of the \mathcal{C}-basis vectors satisfies [\mathbf{x}]_{\mathcal B} = P_{\mathcal B \leftarrow \mathcal C}\,[\mathbf{x}]_{\mathcal C} for every \mathbf{x} \in V. Substituting the first formula into the second (and vice versa) gives [\mathbf{x}]_{\mathcal B} = P_{\mathcal B \leftarrow \mathcal C}P_{\mathcal C \leftarrow \mathcal B}\,[\mathbf{x}]_{\mathcal B}, \qquad [\mathbf{x}]_{\mathcal C} = P_{\mathcal C \leftarrow \mathcal B}P_{\mathcal B \leftarrow \mathcal C}\,[\mathbf{x}]_{\mathcal C} for every \mathbf{x} \in V. A matrix that fixes every coordinate vector in \mathbb{R}^n must be the identity matrix I_n (test it against the standard basis vectors, whose coordinate images run over all of \mathbb{R}^n), so both products equal I_n. Hence P_{\mathcal C \leftarrow \mathcal B} and P_{\mathcal B \leftarrow \mathcal C} are inverse to one another.

Characteristic polynomial (and hence eigenvalues). Write the characteristic polynomial of B using B = P^{-1}AP: \det(B - \lambda I) = \det\!\left(P^{-1}AP - \lambda I\right) = \det\!\left(P^{-1}AP - \lambda P^{-1}P\right) = \det\!\left(P^{-1}(A - \lambda I)P\right). The determinant is multiplicative, so this splits into three factors: \det(B - \lambda I) = \det(P^{-1})\,\det(A - \lambda I)\,\det(P) = \det(A - \lambda I), since \det(P^{-1}) = 1/\det(P) cancels against \det(P). So A and B share the same characteristic polynomial \det(A - \lambda I), and therefore the same roots — the same eigenvalues, each with the same algebraic multiplicity, since multiplicity is read off the same polynomial.

Determinant. Setting \lambda = 0 in the identity just proved gives \det(B) = \det(A) directly. (Equivalently, \det(B) = \det(P^{-1})\det(A)\det(P) = \det(A) by the same multiplicative argument.)

Trace. The characteristic polynomial of an n \times n matrix M has the form \det(M - \lambda I) = (-\lambda)^n + \operatorname{tr}(M)(-\lambda)^{n-1} + \cdots + \det(M), so \operatorname{tr}(M) is exactly the coefficient of (-\lambda)^{n-1}. Since A and B share the same characteristic polynomial, they share that coefficient, so \operatorname{tr}(A) = \operatorname{tr}(B).

Rank. Left-multiplication by the invertible matrix P^{-1} and right-multiplication by the invertible matrix P each preserve rank — multiplying by an invertible matrix on either side sends a basis of the column space to another basis of a column space of the same dimension, and never collapses two independent columns together, since invertible maps are one-to-one. So \operatorname{rank}(B) = \operatorname{rank}(P^{-1}AP) = \operatorname{rank}(AP) = \operatorname{rank}(A).

Why this matters. These quantities are exactly the ones that don't depend on which basis is used to write a linear transformation as a matrix — changing basis replaces A by P^{-1}AP for the change-of-basis matrix P, so \det, \operatorname{tr}, \operatorname{rank}, and the eigenvalues are properties of the underlying transformation itself, not artifacts of coordinates. The converse is false: matrices can share all of these invariants without being similar (a diagonalizable matrix is never similar to a non-diagonalizable one with the same eigenvalues), so this theorem gives necessary conditions for similarity, not sufficient ones.

Fix A and treat \det(AB) as a function of B alone, writing B = \begin{pmatrix} \mathbf{b}_1 & \mathbf{b}_2 & \cdots & \mathbf{b}_n \end{pmatrix} in terms of its columns, so that AB = \begin{pmatrix} A\mathbf{b}_1 & A\mathbf{b}_2 & \cdots & A\mathbf{b}_n \end{pmatrix}.

Case 1: B is singular. Then \det B = 0, and the columns of B are linearly dependent — some \mathbf{b}_k is a linear combination of the others. Because A acts linearly, A\mathbf{b}_k is that same combination of the columns A\mathbf{b}_1, \dots, A\mathbf{b}_n, so the columns of AB are dependent too. A matrix with dependent columns has determinant 0, so \det(AB) = 0 = \det(A) \cdot 0 = \det(A)\det(B). The identity holds in this case regardless of what A is.

Case 2: B is invertible. Then B is a product of elementary matrices, B = E_1 E_2 \cdots E_k, since row-reducing B to the identity records a sequence of elementary row operations, and undoing them (in reverse) rebuilds B from I one elementary factor at a time. Each elementary matrix E scales the determinant of whatever it multiplies by a fixed factor c_E depending only on which operation E performs — a row swap gives c_E = -1, scaling a row by r gives c_E = r, and adding a multiple of one row to another gives c_E = 1 — and in every case that same factor satisfies \det E = c_E \cdot \det I = c_E. So for any matrix M, \det(EM) = c_E \det M = (\det E)(\det M). Applying this one elementary factor at a time, \det(AB) = \det(A E_1 E_2 \cdots E_k) = (\det E_k)\det(AE_1\cdots E_{k-1}) = \cdots = \det(A)\det(E_1)\det(E_2)\cdots\det(E_k). Running the same one-factor-at-a-time collapse on B itself (with A replaced by I) gives \det(B) = \det(E_1)\det(E_2)\cdots\det(E_k), so the product of the \det(E_i)'s appearing above is exactly \det(B), giving \det(AB) = \det(A)\det(B).

Together the two cases cover every B, so the identity holds in general.

Sanity check: take A = B = I_n. Both sides read \det(I_n) = 1 \cdot 1, which checks out. Take B singular and A = I_n: the left side is \det(I_n B) = \det B = 0, matching \det(I_n)\det(B) = 1 \cdot 0.

Both directions lean on one algebraic fact borrowed from determinant theory: for any two n\times n matrices A and B, \det(AB) = (\det A)(\det B).

If A is invertible, then \det A \ne 0. By definition AA^{-1} = I_n. Taking the determinant of both sides and applying the product rule above, \det(A)\det\left(A^{-1}\right) = \det I_n = 1. A product of two real numbers can only equal 1 if neither factor is 0 (anything times 0 is 0, never 1), so \det A \ne 0 — and this same equation already isolates \det\left(A^{-1}\right) = \frac{1}{\det A}, which is the stated corollary.

If \det A \ne 0, then A is invertible. Row-reduce A to an echelon form U. Each elementary row operation used along the way changes \det A by a known nonzero factor — a row swap multiplies the determinant by -1, scaling a row by a nonzero constant c multiplies the determinant by c, and adding a multiple of one row to another leaves the determinant unchanged — so \det U is \det A times a nonzero constant. Since \det A \ne 0 by hypothesis, this forces \det U \ne 0 as well.

U is upper triangular, so \det U is exactly the product of its diagonal entries. For that product to be nonzero, every diagonal entry of U must be nonzero — none of them collapsed to a zero pivot during elimination. An n\times n triangular matrix with n nonzero diagonal entries has a pivot in every row and every column, so U row-reduces further, by scaling each row to make its pivot 1 and clearing every entry above each pivot, all the way down to I_n. Since A was row equivalent to U and U is row equivalent to I_n, A is row equivalent to I_n.

Every elementary row operation is itself invertible — undoing a swap is another swap, undoing a scaling by c\ne0 is scaling by 1/c, undoing a row addition is subtracting the same multiple back off — and each can be realized as left-multiplication by an elementary matrix E_k. Chaining the operations that carried A to I_n gives E_k \cdots E_1 A = I_n, so the product B = E_k\cdots E_1 satisfies BA = I_n. Since B is itself a product of invertible elementary matrices, B is invertible with inverse B^{-1} = E_1^{-1}\cdots E_k^{-1}; multiplying BA = I_n on the left by B^{-1} gives A = B^{-1}, so A is invertible with A^{-1} = B.

Sanity check: for the 1\times 1 case A = [a], \det A = a, and the theorem reduces to the familiar fact that a single number is invertible (has a reciprocal) exactly when it is nonzero — the determinant test is the n\times n generalization of that one observation.

The claim has two parts: each \mathbf{u}_k built this way is orthogonal to every \mathbf{u}_i that came before it, and the running set \{\mathbf{u}_1, \ldots, \mathbf{u}_k\} spans the same subspace as \{\mathbf{v}_1, \ldots, \mathbf{v}_k\} at every stage. Both are proved together by induction on k.

Base case. \mathbf{u}_1 = \mathbf{v}_1, so trivially \operatorname{span}\{\mathbf{u}_1\} = \operatorname{span}\{\mathbf{v}_1\}, and there is no earlier vector to be orthogonal to.

Inductive step. Suppose \{\mathbf{u}_1, \ldots, \mathbf{u}_{k-1}\} is already orthogonal and spans the same set as \{\mathbf{v}_1, \ldots, \mathbf{v}_{k-1}\}. Form \mathbf{u}_k = \mathbf{v}_k - \sum_{i=1}^{k-1} \operatorname{proj}_{\mathbf{u}_i}(\mathbf{v}_k) = \mathbf{v}_k - \sum_{i=1}^{k-1} \frac{\mathbf{v}_k \cdot \mathbf{u}_i}{\mathbf{u}_i \cdot \mathbf{u}_i}\,\mathbf{u}_i.

Orthogonality. Fix any j with 1 \le j \le k-1 and dot both sides with \mathbf{u}_j: \mathbf{u}_k \cdot \mathbf{u}_j = \mathbf{v}_k \cdot \mathbf{u}_j - \sum_{i=1}^{k-1} \frac{\mathbf{v}_k \cdot \mathbf{u}_i}{\mathbf{u}_i \cdot \mathbf{u}_i}\,(\mathbf{u}_i \cdot \mathbf{u}_j). By the inductive hypothesis \{\mathbf{u}_1, \ldots, \mathbf{u}_{k-1}\} is orthogonal, so \mathbf{u}_i \cdot \mathbf{u}_j = 0 for every i \ne j in that sum, and every term except i = j drops out. What's left is \mathbf{u}_k \cdot \mathbf{u}_j = \mathbf{v}_k \cdot \mathbf{u}_j - \frac{\mathbf{v}_k \cdot \mathbf{u}_j}{\mathbf{u}_j \cdot \mathbf{u}_j}\,(\mathbf{u}_j \cdot \mathbf{u}_j) = \mathbf{v}_k \cdot \mathbf{u}_j - \mathbf{v}_k \cdot \mathbf{u}_j = 0. Since j was arbitrary, \mathbf{u}_k is orthogonal to every earlier \mathbf{u}_i, and since \{\mathbf{u}_1, \ldots, \mathbf{u}_{k-1}\} is already pairwise orthogonal, \{\mathbf{u}_1, \ldots, \mathbf{u}_k\} is too. (This step needs \mathbf{u}_j \ne \mathbf{0} for each earlier j, which the spanning argument below guarantees: a zero \mathbf{u}_j would mean \mathbf{v}_j already lay in the span of the vectors before it, contradicting linear independence of the original basis.)

Same span. The formula for \mathbf{u}_k writes \mathbf{v}_k as \mathbf{u}_k plus a linear combination of \mathbf{u}_1, \ldots, \mathbf{u}_{k-1}, i.e. \mathbf{v}_k = \mathbf{u}_k + \sum_{i=1}^{k-1} \frac{\mathbf{v}_k \cdot \mathbf{u}_i}{\mathbf{u}_i \cdot \mathbf{u}_i}\,\mathbf{u}_i. By the inductive hypothesis each \mathbf{u}_i on the right is itself a linear combination of \mathbf{v}_1, \ldots, \mathbf{v}_{k-1}, so \mathbf{v}_k \in \operatorname{span}\{\mathbf{v}_1, \ldots, \mathbf{v}_{k-1}, \mathbf{u}_k\}, and conversely \mathbf{u}_k \in \operatorname{span}\{\mathbf{v}_1, \ldots, \mathbf{v}_k\} directly from its defining formula. Combined with the inductive hypothesis that \operatorname{span}\{\mathbf{u}_1, \ldots, \mathbf{u}_{k-1}\} = \operatorname{span}\{\mathbf{v}_1, \ldots, \mathbf{v}_{k-1}\}, this gives \operatorname{span}\{\mathbf{u}_1, \ldots, \mathbf{u}_k\} = \operatorname{span}\{\mathbf{v}_1, \ldots, \mathbf{v}_k\}.

By induction, both properties hold for every k up to n, so \{\mathbf{u}_1, \ldots, \mathbf{u}_n\} is an orthogonal basis for the same subspace spanned by \{\mathbf{v}_1, \ldots, \mathbf{v}_n\}. None of the \mathbf{u}_k can be \mathbf{0}: that would force \mathbf{v}_k into the span of \mathbf{v}_1, \ldots, \mathbf{v}_{k-1}, contradicting linear independence, so every division by \mathbf{u}_i \cdot \mathbf{u}_i above is division by a positive number.

Normalizing. Once \{\mathbf{u}_1, \ldots, \mathbf{u}_n\} is orthogonal with no zero vector among them, setting \mathbf{q}_k = \mathbf{u}_k / \lVert\mathbf{u}_k\rVert scales each vector to unit length without disturbing the directions, so \{\mathbf{q}_1, \ldots, \mathbf{q}_n\} is orthonormal and spans the same subspace.

(\Leftarrow) n independent eigenvectors give A = PDP^{-1}. Suppose v_1, \dots, v_n are linearly independent eigenvectors of A, with Av_i = \lambda_i v_i. Let P be the matrix with these vectors as its columns, and let D = \operatorname{diag}(\lambda_1, \dots, \lambda_n). Multiplying A into P column by column, AP = A\begin{bmatrix} v_1 & \cdots & v_n \end{bmatrix} = \begin{bmatrix} Av_1 & \cdots & Av_n \end{bmatrix} = \begin{bmatrix} \lambda_1 v_1 & \cdots & \lambda_n v_n \end{bmatrix}. Multiplying P by D on the right scales each column of P by the matching diagonal entry of D, producing the very same matrix: PD = \begin{bmatrix} v_1 & \cdots & v_n \end{bmatrix} \operatorname{diag}(\lambda_1,\dots,\lambda_n) = \begin{bmatrix} \lambda_1 v_1 & \cdots & \lambda_n v_n \end{bmatrix}. So AP = PD. Because P's columns are n linearly independent vectors in \mathbb{R}^n, P is invertible, and right-multiplying both sides by P^{-1} gives A = PDP^{-1}.

(\Rightarrow) A = PDP^{-1} gives n independent eigenvectors. Suppose A = PDP^{-1} with P invertible and D = \operatorname{diag}(\lambda_1, \dots, \lambda_n). Then AP = PD, and reading that equation column by column exactly as above shows Av_i = \lambda_i v_i, where v_i is the i-th column of P. Each v_i is nonzero — a zero column would make P singular — so v_1,\dots,v_n are eigenvectors of A. Since P is invertible, its columns are linearly independent, which produces the needed n independent eigenvectors.

Sanity check: take A = \begin{bmatrix} 4 & 1 \\ 0 & 3 \end{bmatrix}, upper triangular, so its eigenvalues sit on the diagonal: \lambda_1 = 4, \lambda_2 = 3. Solving (A - 4I)v = 0 gives eigenvector v_1 = (1,0), and (A-3I)v = 0 gives v_2 = (1,-1). These two are not scalar multiples of each other, so they're independent, and the theorem guarantees A = PDP^{-1} with P = \begin{bmatrix} 1 & 1 \\ 0 & -1 \end{bmatrix} and D = \begin{bmatrix} 4 & 0 \\ 0 & 3 \end{bmatrix} — which a direct multiplication PDP^{-1} confirms reproduces A.

(\Leftarrow) Orthogonal diagonalizability forces symmetry. Suppose A = QDQ^{\mathsf T} with Q orthogonal and D diagonal. Diagonal matrices equal their own transpose, and transposing a product reverses the order of its factors, so A^{\mathsf T} = (QDQ^{\mathsf T})^{\mathsf T} = (Q^{\mathsf T})^{\mathsf T}D^{\mathsf T}Q^{\mathsf T} = QDQ^{\mathsf T} = A. So A is symmetric. The rest of the proof handles the harder direction.

Symmetric matrices have only real eigenvalues. Let \lambda be an eigenvalue of A, allowing for the moment that it might be complex, with eigenvector v (possibly with complex entries), so Av = \lambda v. Let \bar v denote the entrywise complex conjugate of v, and consider the scalar \bar v^{\mathsf T} A v. Computing it one way, \bar v^{\mathsf T} A v = \bar v^{\mathsf T}(\lambda v) = \lambda (\bar v^{\mathsf T} v) = \lambda \lVert v \rVert^2, since \bar v^{\mathsf T} v = \sum_i \overline{v_i} v_i = \sum_i |v_i|^2 = \lVert v \rVert^2 is real and positive (v \neq 0, being an eigenvector). Computing the same scalar the other way, using A^{\mathsf T} = A and that \bar v^{\mathsf T} A v is a 1\times 1 matrix and so equal to its own transpose, \bar v^{\mathsf T} A v = \left(\bar v^{\mathsf T} A v\right)^{\mathsf T} = v^{\mathsf T} A^{\mathsf T} \bar v = v^{\mathsf T} A \bar v. Taking the complex conjugate of Av = \lambda v gives A\bar v = \bar\lambda \bar v (since A has real entries, conjugation passes through it untouched), so v^{\mathsf T} A \bar v = v^{\mathsf T}(\bar\lambda \bar v) = \bar\lambda (v^{\mathsf T}\bar v) = \bar\lambda \lVert v\rVert^2, using v^{\mathsf T}\bar v = \overline{\bar v^{\mathsf T} v} = \lVert v\rVert^2 again. The two computations of \bar v^{\mathsf T} A v must agree: \lambda \lVert v \rVert^2 = \bar\lambda \lVert v \rVert^2. Since \lVert v \rVert^2 \neq 0, this forces \lambda = \bar\lambda, i.e. \lambda is real. So every eigenvalue of A is real, and consequently every eigenvalue has a real eigenvector (a real matrix minus a real multiple of I_n has a real null space).

Eigenvectors for distinct eigenvalues are orthogonal. Let Av_1 = \lambda_1 v_1 and Av_2 = \lambda_2 v_2 with \lambda_1 \neq \lambda_2. Using symmetry, \lambda_1 (v_1 \cdot v_2) = (Av_1) \cdot v_2 = v_1^{\mathsf T}A^{\mathsf T} v_2 = v_1^{\mathsf T}Av_2 = v_1 \cdot (Av_2) = \lambda_2(v_1 \cdot v_2). So (\lambda_1 - \lambda_2)(v_1 \cdot v_2) = 0, and since \lambda_1 \neq \lambda_2, this forces v_1 \cdot v_2 = 0.

Building Q by induction on n. The base case n=1 is trivial: any 1\times 1 matrix is already diagonal, and Q = [1] is orthogonal. For the inductive step, assume every symmetric (n-1)\times(n-1) matrix is orthogonally diagonalizable, and let A be a symmetric n \times n matrix. By the real-eigenvalue fact above, A has a real eigenvalue \lambda_1 with a real, nonzero eigenvector; rescale it to a unit vector q_1, so Aq_1 = \lambda_1 q_1 and \lVert q_1 \rVert = 1. Extend \{q_1\} to an orthonormal basis \{q_1, q_2, \dots, q_n\} of \mathbb{R}^n (extend to any basis and apply Gram–Schmidt, which leaves q_1 fixed since it is already a unit vector orthogonal to nothing else yet chosen), and let P be the orthogonal matrix with these vectors as columns.

The subspace W = \operatorname{span}(q_2,\dots,q_n) = q_1^\perp is invariant under A: for w \in W, (Aw)\cdot q_1 = w \cdot (Aq_1) = w \cdot (\lambda_1 q_1) = \lambda_1(w\cdot q_1) = 0, using symmetry in the first step exactly as above, so Aw is again orthogonal to q_1, i.e. Aw \in W. Consequently P^{\mathsf T}AP has the block form P^{\mathsf T}AP = \begin{bmatrix} \lambda_1 & 0 \\ 0 & A_1 \end{bmatrix} for some symmetric (n-1)\times(n-1) matrix A_1: the first column of P^{\mathsf T}AP is P^{\mathsf T}(Aq_1) = P^{\mathsf T}(\lambda_1 q_1) = \lambda_1 e_1 (since P^{\mathsf T}q_1 = e_1, q_1 being the first column of the orthogonal matrix P), giving the zero block below \lambda_1; and P^{\mathsf T}AP is symmetric because A is, which forces the zero block to the right of \lambda_1 as well. By the inductive hypothesis, A_1 = Q_1D_1Q_1^{\mathsf T} for some orthogonal (n-1)\times(n-1) matrix Q_1 and diagonal D_1. Setting Q = P\begin{bmatrix} 1 & 0 \\ 0 & Q_1 \end{bmatrix}, \qquad D = \begin{bmatrix} \lambda_1 & 0 \\ 0 & D_1 \end{bmatrix}, the block-diagonal factor is orthogonal (its columns are orthonormal, being e_1 together with the orthonormal columns of Q_1), so Q is a product of orthogonal matrices and hence orthogonal itself. Unwinding the block product, Q^{\mathsf T}AQ = \begin{bmatrix} 1 & 0 \\ 0 & Q_1^{\mathsf T} \end{bmatrix}P^{\mathsf T}AP\begin{bmatrix} 1 & 0 \\ 0 & Q_1 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & Q_1^{\mathsf T} \end{bmatrix}\begin{bmatrix} \lambda_1 & 0 \\ 0 & A_1 \end{bmatrix}\begin{bmatrix} 1 & 0 \\ 0 & Q_1 \end{bmatrix} = \begin{bmatrix} \lambda_1 & 0 \\ 0 & Q_1^{\mathsf T}A_1Q_1 \end{bmatrix} = D, so A = QDQ^{\mathsf T} with Q orthogonal and D diagonal, completing the induction.

Sanity check: take the symmetric matrix A = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}. Its characteristic equation is (2-\lambda)^2 - 1 = 0, so \lambda_1 = 3 and \lambda_2 = 1 — both real, as guaranteed. Solving (A-3I)v=0 gives v_1 = (1,1), and (A-I)v=0 gives v_2 = (1,-1); these two are orthogonal (v_1 \cdot v_2 = 1 - 1 = 0), exactly as the theorem predicts for eigenvectors of distinct eigenvalues. Normalizing gives q_1 = \frac{1}{\sqrt2}(1,1) and q_2 = \frac{1}{\sqrt2}(1,-1), and setting Q = \begin{bmatrix} 1/\sqrt2 & 1/\sqrt2 \\ 1/\sqrt2 & -1/\sqrt2 \end{bmatrix}, D = \begin{bmatrix} 3 & 0 \\ 0 & 1 \end{bmatrix}, a direct multiplication confirms QDQ^{\mathsf T} = A.

Every known proof leans on machinery outside this course — complex analysis (Liouville's theorem: a bounded entire function is constant, applied to 1/f), topology (a degree-n map wraps the plane around itself n times, so it must hit 0), or Galois theory. None of those tools are available yet, so the result is taken on faith here, the way it is in every first course that uses it. What this course can do with it: combined with the Factor Theorem, it guarantees a degree-n polynomial factors completely into n linear factors over the complex numbers — that consequence, the Linear Factorization Theorem, is used freely and does have its own proof in the registry.

By induction on k, we show that after k exchange steps, some relabeling of the spanning set has \{v_1, \dots, v_k, u_{k+1}, \dots, u_m\} still spanning V — provided k \le n and k \le m at each step.

Base case (k=0). The original spanning set \{u_1,\dots,u_m\} spans V by hypothesis.

Inductive step. Suppose \{v_1,\dots,v_k,u_{k+1},\dots,u_m\} spans V, with k < n. Since this set spans V, write v_{k+1} = c_1v_1 + \cdots + c_kv_k + d_{k+1}u_{k+1} + \cdots + d_mu_m. The independence of \{v_1,\dots,v_n\} rules out d_{k+1}=\cdots=d_m=0 (that would make v_{k+1} a combination of v_1,\dots,v_k, contradicting independence) — so some d_j \ne 0 for j > k. Relabel so j=k+1; solve for u_{k+1}: u_{k+1} = \frac{1}{d_{k+1}}\Big(v_{k+1} - c_1v_1 - \cdots - c_kv_k - d_{k+2}u_{k+2} - \cdots - d_mu_m\Big). This equation shows u_{k+1} lies in the span of \{v_1,\dots,v_{k+1},u_{k+2},\dots,u_m\}, so that set spans everything the previous set did — namely all of V.

Why the induction must stop by k=m. Each step consumes one u_j and requires j > k to exist among u_{k+1},\dots,u_m — that is, it requires k < m. If n > m, the step k=m would demand exchanging in v_{m+1} with no u_j left to remove, but the set \{v_1,\dots,v_m\} already spans V at that point, making v_{m+1} a combination of v_1,\dots,v_m — contradicting the independence of \{v_1,\dots,v_n\}. So the process cannot reach k=n unless n \le m. \blacksquare

Corollary (well-definedness of dimension). If \{u_1,\dots,u_m\} and \{v_1,\dots,v_n\} are both bases of V, apply the lemma twice: m spans and n is independent gives n \le m; n spans and m is independent gives m \le n. Hence m = n — every basis of V has the same size, which is exactly what makes \dim V a well-defined number rather than a choice-dependent one.

Let \{x_1,\dots,x_k\} be a basis of U \cap W (dimension k). Since U \cap W \subseteq U, extend this to a basis \{x_1,\dots,x_k, u_1,\dots,u_p\} of U (so \dim U = k+p), and independently extend it to a basis \{x_1,\dots,x_k, w_1,\dots,w_q\} of W (so \dim W = k+q).

Claim: \{x_1,\dots,x_k,u_1,\dots,u_p,w_1,\dots,w_q\} is a basis of U+W. It spans U+W immediately, since every element of U+W is a sum of an element of U (a combination of x's and u's) and an element of W (a combination of x's and w's).

For independence, suppose \sum_i a_ix_i + \sum_j b_ju_j + \sum_l c_lw_l = \mathbf 0. Rearranging, \sum_l c_lw_l = -\sum_i a_ix_i - \sum_j b_ju_j, and the right side lies in U (a combination of x's and u's), so the left side \sum_l c_lw_l — itself already visibly in W — must lie in U \cap W. But \{x_1,\dots,x_k\} is a basis of U \cap W, and \{x_1,\dots,x_k,w_1,\dots,w_q\} is independent (it's a basis of W), so writing \sum_l c_lw_l as a combination of x's forces every c_l = 0. With the c_l's gone, \sum_i a_ix_i + \sum_j b_ju_j = \mathbf 0 follows from the independence of \{x_1,\dots,x_k,u_1,\dots,u_p\} (a basis of U), forcing every a_i and b_j to 0 too.

Counting. The basis of U+W just constructed has k+p+q vectors, so \dim(U+W) = k+p+q = (k+p) + (k+q) - k = \dim U + \dim W - \dim(U\cap W). \blacksquare

Sanity check. When U \cap W = \{\mathbf 0\} (so k=0), the formula reduces to \dim(U+W) = \dim U + \dim W — the sum is direct, and dimensions simply add, matching the direct-sum decomposition every vector in U+W then has.

\overline T is well-defined. If v + \ker T = v' + \ker T (the same coset), then v - v' \in \ker T, so T(v-v') = \mathbf 0, giving T(v) = T(v') — the output doesn't depend on which coset representative was chosen.

\overline T is linear. Immediate from T's own linearity: \overline T\big((v+\ker T) + (v'+\ker T)\big) = \overline T\big((v+v')+\ker T\big) = T(v+v') = T(v)+T(v') = \overline T(v+\ker T) + \overline T(v'+\ker T), and similarly for scalar multiples.

\overline T is one-to-one. Suppose \overline T(v+\ker T) = \mathbf 0. Then T(v) = \mathbf 0, so v \in \ker T, so v + \ker T is the zero coset. A linear map with trivial kernel is one-to-one (the standard kernel test), so \overline T is one-to-one.

\overline T is onto \operatorname{im} T. Every element of \operatorname{im} T is T(v) for some v \in V, and \overline T(v+\ker T) = T(v) by definition — so every element of \operatorname{im} T is hit.

A linear map that is both one-to-one and onto is an isomorphism, so V/\ker T \cong \operatorname{im} T. \blacksquare

Why this is rank-nullity in disguise. Taking dimensions of both sides (isomorphic spaces have equal dimension) gives \dim(V/\ker T) = \dim(\operatorname{im} T). Since \dim(V/\ker T) = \dim V - \dim(\ker T) (the quotient-space dimension formula), this is exactly \dim V - \dim(\ker T) = \dim(\operatorname{im} T) — the rank-nullity theorem, recovered as a corollary rather than assumed independently.

Let k = \dim\left(\operatorname{Nul}A\right) and pick a basis \{\mathbf{v}_1,\dots,\mathbf{v}_k\} for \operatorname{Nul}A, the set of vectors in \mathbb{R}^n that A sends to \mathbf{0}. Since any basis for a subspace of \mathbb{R}^n extends to a basis of the whole space, choose vectors \mathbf{v}_{k+1},\dots,\mathbf{v}_n so that \{\mathbf{v}_1,\dots,\mathbf{v}_n\} is a basis for \mathbb{R}^n. The claim is that the n-k image vectors A\mathbf{v}_{k+1},\dots,A\mathbf{v}_n form a basis for \operatorname{Col}A, which pins \operatorname{rank}(A) = n-k and finishes the proof.

Spanning. Every \mathbf{b}\in\operatorname{Col}A has the form A\mathbf{x} for some \mathbf{x}\in\mathbb{R}^n. Write \mathbf{x} in the extended basis as \mathbf{x} = c_1\mathbf{v}_1 + \cdots + c_n\mathbf{v}_n. Applying A and using linearity, \mathbf{b} = A\mathbf{x} = c_1A\mathbf{v}_1 + \cdots + c_kA\mathbf{v}_k + c_{k+1}A\mathbf{v}_{k+1} + \cdots + c_nA\mathbf{v}_n. The first k terms vanish because \mathbf{v}_1,\dots,\mathbf{v}_k \in \operatorname{Nul}A, leaving \mathbf{b} = c_{k+1}A\mathbf{v}_{k+1} + \cdots + c_nA\mathbf{v}_n. So the n-k image vectors already span \operatorname{Col}A.

Independence. Suppose c_{k+1}A\mathbf{v}_{k+1} + \cdots + c_nA\mathbf{v}_n = \mathbf{0}. By linearity this is A(c_{k+1}\mathbf{v}_{k+1} + \cdots + c_n\mathbf{v}_n) = \mathbf{0}, which puts the vector \mathbf{w} = c_{k+1}\mathbf{v}_{k+1} + \cdots + c_n\mathbf{v}_n inside \operatorname{Nul}A. Since \{\mathbf{v}_1,\dots,\mathbf{v}_k\} is a basis for \operatorname{Nul}A, \mathbf{w} also equals some combination d_1\mathbf{v}_1 + \cdots + d_k\mathbf{v}_k. Subtracting the two expressions for \mathbf{w} gives d_1\mathbf{v}_1 + \cdots + d_k\mathbf{v}_k - c_{k+1}\mathbf{v}_{k+1} - \cdots - c_n\mathbf{v}_n = \mathbf{0}, a linear relation among all n vectors of the basis \{\mathbf{v}_1,\dots,\mathbf{v}_n\}. Basis vectors are linearly independent, so every coefficient here is 0 — in particular c_{k+1} = \cdots = c_n = 0. Only the trivial combination of A\mathbf{v}_{k+1},\dots,A\mathbf{v}_n gives \mathbf{0}, so these vectors are linearly independent.

Together, spanning and independence make \{A\mathbf{v}_{k+1},\dots, A\mathbf{v}_n\} a basis for \operatorname{Col}A, so \operatorname{rank}(A) = \dim\left(\operatorname{Col}A\right) = n-k. Moving k to the other side recovers \operatorname{rank}(A) + \dim\left(\operatorname{Nul}A\right) = n.

Sanity check: for the 3\times 3 identity matrix, \operatorname{Nul}A = \{\mathbf{0}\}, so k = 0 and \operatorname{rank}(A) = 3 = n, matching the fact that the identity is invertible and its columns already span \mathbb{R}^3. At the other extreme, the 3\times 3 zero matrix has \operatorname{Nul}A = \mathbb{R}^3, so k=3 and \operatorname{rank}(A) = 0 — no columns to span anything — and 0 + 3 = 3 still checks out.

Existence. For each i, define \varphi_i on the basis by \varphi_i(b_j) = \delta_{ij} and extend linearly to all of V — every linear map is uniquely determined by its values on a basis, so this defines a genuine linear functional \varphi_i \in V^{*} for each i.

Independence. Suppose c_1\varphi_1 + \cdots + c_n\varphi_n = 0 (the zero functional). Evaluate both sides at b_j: 0 = (c_1\varphi_1+\cdots+c_n\varphi_n)(b_j) = c_1\varphi_1(b_j) + \cdots + c_n\varphi_n(b_j) = c_j, since \varphi_i(b_j)=\delta_{ij} kills every term except i=j. This holds for every j, so every c_j = 0 — the set is independent.

Spanning. \dim V^{*} = \dim V = n (section 1's coordinate-space identification), and n independent vectors in an n-dimensional space automatically form a basis (the exchange lemma's corollary). So \{\varphi_1,\dots,\varphi_n\} spans V^{*} too.

Uniqueness. If \{\psi_1,\dots,\psi_n\} is any other basis satisfying \psi_i(b_j)=\delta_{ij}, then \psi_i - \varphi_i vanishes on every b_j, hence on all of V (linearity), so \psi_i=\varphi_i for every i. \blacksquare

Extend a basis \{w_1,\dots,w_k\} of W to a basis \{w_1,\dots,w_k,v_{k+1},\dots,v_n\} of V (chapter 01's basis-extension construction), and let \{\varphi_1,\dots,\varphi_k,\psi_{k+1},\dots,\psi_n\} be the corresponding dual basis of V^{*}.

Claim: W^{\circ} = \operatorname{span}\{\psi_{k+1},\dots,\psi_n\}. Each \psi_j (j > k) vanishes on every w_i (i \le k) by the dual basis's defining property \psi_j(w_i) = 0 for j \ne i — and since j > k \ge i always, j \ne i always holds. So \psi_j vanishes on the basis of W, hence on all of W (linearity): each \psi_j \in W^{\circ}. Conversely, any \varphi \in W^{\circ} writes as \varphi = \sum_i c_i\varphi_i + \sum_j d_j\psi_j in the dual basis; evaluating at each w_i forces c_i = \varphi(w_i) = 0 (since \varphi annihilates W), leaving \varphi = \sum_j d_j\psi_j \in \operatorname{span}\{\psi_{k+1},\dots,\psi_n\}.

Counting. The set \{\psi_{k+1},\dots,\psi_n\} has n-k vectors, and it's independent (a subset of the independent dual basis), so \dim(W^{\circ}) = n-k = \dim V - \dim W. \blacksquare

Expand Q(\mathbf u+\mathbf v) = B(\mathbf u+\mathbf v,\mathbf u+\mathbf v) using bilinearity in both arguments: Q(\mathbf u+\mathbf v) = B(\mathbf u,\mathbf u) + B(\mathbf u,\mathbf v) + B(\mathbf v,\mathbf u) + B(\mathbf v,\mathbf v). Since B is symmetric, B(\mathbf u,\mathbf v) = B(\mathbf v,\mathbf u), so the two middle terms combine: Q(\mathbf u+\mathbf v) = Q(\mathbf u) + 2B(\mathbf u,\mathbf v) + Q(\mathbf v). Solving for B(\mathbf u,\mathbf v) gives B(\mathbf u,\mathbf v) = \tfrac12\big(Q(\mathbf u+\mathbf v) - Q(\mathbf u) - Q(\mathbf v)\big), which requires dividing by 2 — exactly the reason this identity statement assumes 1+1 \ne 0 in the underlying field. Since the right-hand side depends only on values of Q, any two symmetric bilinear forms producing the same Q must be equal, making the correspondence B \leftrightarrow Q injective; it is onto by construction, since every quadratic form arises as Q(\mathbf v) = B(\mathbf v,\mathbf v) for its own associated symmetric B. \blacksquare

Suppose a form Q diagonalizes as \sum_{i=1}^{p} x_i^2 - \sum_{i=p+1}^{p+q} x_i^2 in coordinates (x_1,\dots,x_n) (basis \{e_i\}) and also as \sum_{i=1}^{p'} y_i^2 - \sum_{i=p'+1}^{p'+q'} y_i^2 in coordinates (y_1,\dots,y_n) (basis \{f_i\}). Suppose toward contradiction p \ne p'; WLOG p > p'.

Let P = \operatorname{span}\{e_1,\dots,e_p\} (dimension p, where Q is positive on every nonzero vector) and let N' = \operatorname{span}\{f_{p'+1},\dots,f_n\} (dimension n-p', where Q is negative semidefinite). Since p + (n-p') > n (using p > p'), the dimension formula forces P \cap N' \ne \{\mathbf 0\} — pick a nonzero \mathbf v in that intersection.

Being in P, \mathbf v \ne \mathbf 0 gives Q(\mathbf v) > 0. Being in N', Q(\mathbf v) \le 0. These contradict each other, so the assumption p > p' is false. By symmetry p' > p is also false, forcing p = p'. An identical argument (swapping the roles of positive and negative) gives q = q', and since n_0 = n - p - q is then also determined, the full signature (n_+,n_-,n_0) = (p,q,n_0) is the same for both diagonalizations. \blacksquare

Expand each squared norm using the inner product directly: \lVert\mathbf u+\mathbf v\rVert^2 = \langle\mathbf u+\mathbf v,\mathbf u+\mathbf v\rangle = \langle\mathbf u,\mathbf u\rangle + \langle\mathbf u,\mathbf v\rangle + \langle\mathbf v,\mathbf u\rangle + \langle\mathbf v,\mathbf v\rangle, \lVert\mathbf u-\mathbf v\rVert^2 = \langle\mathbf u-\mathbf v,\mathbf u-\mathbf v\rangle = \langle\mathbf u,\mathbf u\rangle - \langle\mathbf u,\mathbf v\rangle - \langle\mathbf v,\mathbf u\rangle + \langle\mathbf v,\mathbf v\rangle. Adding the two expansions, the cross terms \pm\langle\mathbf u,\mathbf v\rangle and \pm\langle\mathbf v,\mathbf u\rangle cancel exactly, leaving \lVert\mathbf u+\mathbf v\rVert^2 + \lVert\mathbf u-\mathbf v\rVert^2 = 2\langle\mathbf u,\mathbf u\rangle + 2\langle\mathbf v,\mathbf v\rangle = 2\lVert\mathbf u\rVert^2 + 2\lVert\mathbf v\rVert^2. Since this identity is a direct consequence of the inner product's own bilinearity (or sesquilinearity) and symmetry, any norm built as \lVert\mathbf v\rVert=\sqrt{\langle\mathbf v,\mathbf v\rangle} must satisfy it — so a norm violating the identity for even one pair of vectors is proof by contradiction that no inner product could have produced it. \blacksquare

If \mathbf{v} = \mathbf{0} both sides are 0 and the inequality holds trivially, so assume \mathbf{v} \neq \mathbf{0}.

Build a function of a single real variable t by looking at the squared length of \mathbf{u} - t\mathbf{v}. A squared length can never be negative, so for every t, 0 \le \lVert\mathbf{u} - t\mathbf{v}\rVert^2 = (\mathbf{u} - t\mathbf{v})\cdot(\mathbf{u} - t\mathbf{v}).

Expand the dot product using bilinearity: 0 \le \mathbf{u}\cdot\mathbf{u} - 2t\,(\mathbf{u}\cdot\mathbf{v}) + t^2\,(\mathbf{v}\cdot\mathbf{v}) = \lVert\mathbf{v}\rVert^2\,t^2 - 2(\mathbf{u}\cdot\mathbf{v})\,t + \lVert\mathbf{u}\rVert^2.

This is a quadratic in t with positive leading coefficient \lVert\mathbf{v}\rVert^2 (since \mathbf{v} \neq \mathbf{0}), and it never dips below 0 — so it can have at most one real root, meaning its discriminant cannot be positive: \left(-2(\mathbf{u}\cdot\mathbf{v})\right)^2 - 4\lVert\mathbf{v}\rVert^2\lVert\mathbf{u}\rVert^2 \le 0.

Simplify: 4(\mathbf{u}\cdot\mathbf{v})^2 \le 4\lVert\mathbf{u}\rVert^2\lVert\mathbf{v}\rVert^2 \quad\Longrightarrow\quad (\mathbf{u}\cdot\mathbf{v})^2 \le \lVert\mathbf{u}\rVert^2\lVert\mathbf{v}\rVert^2.

Taking square roots of both (nonnegative) sides gives |\mathbf{u}\cdot\mathbf{v}| \le \lVert\mathbf{u}\rVert\,\lVert\mathbf{v}\rVert.

Equality case. The discriminant is exactly 0 precisely when the quadratic touches 0 at its unique root t_0, i.e. when \lVert\mathbf{u} - t_0\mathbf{v}\rVert^2 = 0 for some t_0 — which forces \mathbf{u} - t_0\mathbf{v} = \mathbf{0}, so \mathbf{u} = t_0\mathbf{v}. Equality in the inequality therefore holds exactly when \mathbf{u} is a scalar multiple of \mathbf{v} (covering \mathbf{u} = \mathbf{0} as the t_0 = 0 case).

Sanity check: take \mathbf{u} = \mathbf{v}. Then the left side is |\mathbf{u}\cdot\mathbf{u}| = \lVert\mathbf{u}\rVert^2 and the right side is \lVert\mathbf{u}\rVert\,\lVert\mathbf{u}\rVert = \lVert\mathbf{u}\rVert^2 — equality, exactly as the parallel case demands since a vector is trivially a scalar multiple of itself.

Write \hat{\mathbf v} = \operatorname{proj}_W(\mathbf v) for the orthogonal projection of \mathbf v onto W, and recall the defining property of that projection: the residual \mathbf v - \hat{\mathbf v} is orthogonal to every vector in W, i.e. \mathbf v - \hat{\mathbf v} \in W^\perp.

Let \mathbf w be any vector in W with \mathbf w \ne \hat{\mathbf v}. Split the error \mathbf v - \mathbf w into two pieces by inserting and subtracting \hat{\mathbf v}: \mathbf v - \mathbf w = (\mathbf v - \hat{\mathbf v}) + (\hat{\mathbf v} - \mathbf w). The first piece, \mathbf v - \hat{\mathbf v}, lies in W^\perp by the projection property above. The second piece, \hat{\mathbf v} - \mathbf w, is a difference of two vectors already in W, so it lies in W itself (subspaces are closed under subtraction). These two pieces are therefore orthogonal to each other, and the Pythagorean theorem for orthogonal vectors gives \lVert\mathbf v - \mathbf w\rVert^2 = \lVert\mathbf v - \hat{\mathbf v}\rVert^2 + \lVert\hat{\mathbf v} - \mathbf w\rVert^2.

Since \mathbf w \ne \hat{\mathbf v}, the second term \lVert\hat{\mathbf v} - \mathbf w\rVert^2 is strictly positive, so \lVert\mathbf v - \mathbf w\rVert^2 > \lVert\mathbf v - \hat{\mathbf v}\rVert^2, and taking square roots (both sides are nonnegative) gives \lVert\mathbf v - \mathbf w\rVert > \lVert\mathbf v - \hat{\mathbf v}\rVert. Because \mathbf w was an arbitrary point of W other than \hat{\mathbf v}, no other point of W can match or beat the distance achieved by \hat{\mathbf v} — so \hat{\mathbf v} is the unique closest point of W to \mathbf v.

Existence. Fix an orthonormal basis \{\mathbf e_1,\dots,\mathbf e_n\} of V (guaranteed to exist by running Gram-Schmidt on any basis). Define \mathbf w = \sum_{i=1}^n \overline{\varphi(\mathbf e_i)}\,\mathbf e_i (the conjugate is only needed over \mathbb C; over \mathbb R it has no effect). For any \mathbf v = \sum_j v_j \mathbf e_j, \langle\mathbf v,\mathbf w\rangle = \Big\langle \sum_j v_j\mathbf e_j,\ \sum_i \overline{\varphi(\mathbf e_i)}\mathbf e_i\Big\rangle = \sum_{i,j} v_j\,\varphi(\mathbf e_i)\,\langle\mathbf e_j,\mathbf e_i\rangle, using conjugate-linearity in the second argument to bring \overline{\varphi(\mathbf e_i)} back out as \varphi(\mathbf e_i). Orthonormality collapses the double sum to only the i=j terms: \langle\mathbf v,\mathbf w\rangle = \sum_j v_j\,\varphi(\mathbf e_j) = \varphi\Big(\sum_j v_j\mathbf e_j\Big) = \varphi(\mathbf v), using linearity of \varphi in the last step. So \mathbf w represents \varphi as claimed.

Uniqueness. Suppose \mathbf w_1 and \mathbf w_2 both represent \varphi: \langle\mathbf v,\mathbf w_1\rangle = \langle\mathbf v,\mathbf w_2\rangle for every \mathbf v. Then \langle\mathbf v,\mathbf w_1-\mathbf w_2\rangle = 0 for every \mathbf v, in particular for \mathbf v = \mathbf w_1-\mathbf w_2 itself: \langle\mathbf w_1-\mathbf w_2,\ \mathbf w_1-\mathbf w_2\rangle = 0. Positive definiteness forces \mathbf w_1-\mathbf w_2 = \mathbf 0, so \mathbf w_1=\mathbf w_2.

Basis-independence. The vector \mathbf w is uniquely determined by \varphi and the inner product alone, by the uniqueness argument just given — regardless of which orthonormal basis was used to construct it in the existence argument, every such basis must produce the same \mathbf w, since any two representing vectors for the same \varphi are forced to coincide. \blacksquare

Let n = \dim V \ge 1 and pick any nonzero vector \mathbf v \in V. The n+1 vectors \mathbf v, T\mathbf v, T^2\mathbf v, \dots, T^n\mathbf v cannot be linearly independent, since V has dimension only n. So there exist scalars c_0,c_1,\dots,c_n, not all zero, with c_0\mathbf v + c_1T\mathbf v + \cdots + c_nT^n\mathbf v = \mathbf 0. Let k be the largest index with c_k \ne 0 (so k \ge 1, since if only c_0 \ne 0 then c_0\mathbf v = \mathbf 0 would force \mathbf v = \mathbf 0, contradicting the choice of \mathbf v). Treat c_0 + c_1x + \cdots + c_kx^k as a polynomial in x; by the fundamental theorem of algebra it factors completely over \mathbb C: c_0 + c_1x + \cdots + c_kx^k = c_k(x-\lambda_1)(x-\lambda_2)\cdots(x-\lambda_k) for some complex numbers \lambda_1,\dots,\lambda_k (not necessarily distinct). Substituting the operator T for x (legitimate, since this is just a statement about how the polynomial's coefficients combine powers of T) gives \mathbf 0 = c_0\mathbf v + \cdots + c_kT^k\mathbf v = c_k(T-\lambda_1I)(T-\lambda_2I)\cdots(T-\lambda_kI)\mathbf v. Since c_k \ne 0, the product of operators (T-\lambda_1I)\cdots(T-\lambda_kI) sends \mathbf v \ne \mathbf 0 to \mathbf 0. At least one of the factors (T-\lambda_jI) must therefore fail to be injective — if every factor were injective, their composition would be injective too, unable to send a nonzero vector to zero. A non-injective (T-\lambda_jI) means \lambda_j is an eigenvalue of T. \blacksquare

Induct on n = \dim V. For n=1, every 1\times1 matrix is trivially upper triangular, so any orthonormal basis works.

For the inductive step, assume the result for every space of dimension less than n. By the existence-of-eigenvalue theorem, T has an eigenvalue \lambda with eigenvector \mathbf u; normalize it to \lVert\mathbf u\rVert=1. Let U = \text{span}\{\mathbf u\}, so U^\perp has dimension n-1 (chapter 05's direct-sum decomposition).

U^\perp is T^{*}-invariant: for \mathbf w \in U^\perp, \langle T^{*}\mathbf w,\mathbf u\rangle = \langle\mathbf w,T\mathbf u\rangle = \langle\mathbf w,\lambda\mathbf u\rangle = \overline\lambda\langle \mathbf w,\mathbf u\rangle = 0, so T^{*}\mathbf w \in U^\perp too. Define S: U^\perp \to U^\perp by restricting T^{*}, take ITS adjoint S^{*} (an operator on U^\perp), and observe S^{*} agrees with T restricted to U^\perp followed by projection back onto U^\perp — concretely, U^\perp is T-invariant up to that projection, which is exactly what's needed to apply the inductive hypothesis to the restriction of T to U^\perp (dimension n-1).

By induction, U^\perp has an orthonormal basis \mathbf e_2,\dots,\mathbf e_n relative to which this restricted operator's matrix is upper triangular. Then \{\mathbf u,\mathbf e_2,\dots,\mathbf e_n\} is an orthonormal basis of V, and T's matrix relative to it is upper triangular: the first column is (\lambda,0,\dots,0) since T\mathbf u=\lambda\mathbf u, and every other column has zeros below the diagonal by the inductive hypothesis applied to the restriction. \blacksquare

(\Leftarrow) Orthogonal diagonalizability forces symmetry. Suppose A = QDQ^{\mathsf T} with Q orthogonal and D diagonal. Diagonal matrices equal their own transpose, and transposing a product reverses the order of its factors, so A^{\mathsf T} = (QDQ^{\mathsf T})^{\mathsf T} = (Q^{\mathsf T})^{\mathsf T}D^{\mathsf T}Q^{\mathsf T} = QDQ^{\mathsf T} = A. So A is symmetric. The rest of the proof handles the harder direction.

Symmetric matrices have only real eigenvalues. Let \lambda be an eigenvalue of A, allowing for the moment that it might be complex, with eigenvector v (possibly with complex entries), so Av = \lambda v. Let \bar v denote the entrywise complex conjugate of v, and consider the scalar \bar v^{\mathsf T} A v. Computing it one way, \bar v^{\mathsf T} A v = \bar v^{\mathsf T}(\lambda v) = \lambda (\bar v^{\mathsf T} v) = \lambda \lVert v \rVert^2, since \bar v^{\mathsf T} v = \sum_i \overline{v_i} v_i = \sum_i |v_i|^2 = \lVert v \rVert^2 is real and positive (v \neq 0, being an eigenvector). Computing the same scalar the other way, using A^{\mathsf T} = A and that \bar v^{\mathsf T} A v is a 1\times 1 matrix and so equal to its own transpose, \bar v^{\mathsf T} A v = \left(\bar v^{\mathsf T} A v\right)^{\mathsf T} = v^{\mathsf T} A^{\mathsf T} \bar v = v^{\mathsf T} A \bar v. Taking the complex conjugate of Av = \lambda v gives A\bar v = \bar\lambda \bar v (since A has real entries, conjugation passes through it untouched), so v^{\mathsf T} A \bar v = v^{\mathsf T}(\bar\lambda \bar v) = \bar\lambda (v^{\mathsf T}\bar v) = \bar\lambda \lVert v\rVert^2, using v^{\mathsf T}\bar v = \overline{\bar v^{\mathsf T} v} = \lVert v\rVert^2 again. The two computations of \bar v^{\mathsf T} A v must agree: \lambda \lVert v \rVert^2 = \bar\lambda \lVert v \rVert^2. Since \lVert v \rVert^2 \neq 0, this forces \lambda = \bar\lambda, i.e. \lambda is real. So every eigenvalue of A is real, and consequently every eigenvalue has a real eigenvector (a real matrix minus a real multiple of I_n has a real null space).

Eigenvectors for distinct eigenvalues are orthogonal. Let Av_1 = \lambda_1 v_1 and Av_2 = \lambda_2 v_2 with \lambda_1 \neq \lambda_2. Using symmetry, \lambda_1 (v_1 \cdot v_2) = (Av_1) \cdot v_2 = v_1^{\mathsf T}A^{\mathsf T} v_2 = v_1^{\mathsf T}Av_2 = v_1 \cdot (Av_2) = \lambda_2(v_1 \cdot v_2). So (\lambda_1 - \lambda_2)(v_1 \cdot v_2) = 0, and since \lambda_1 \neq \lambda_2, this forces v_1 \cdot v_2 = 0.

Building Q by induction on n. The base case n=1 is trivial: any 1\times 1 matrix is already diagonal, and Q = [1] is orthogonal. For the inductive step, assume every symmetric (n-1)\times(n-1) matrix is orthogonally diagonalizable, and let A be a symmetric n \times n matrix. By the real-eigenvalue fact above, A has a real eigenvalue \lambda_1 with a real, nonzero eigenvector; rescale it to a unit vector q_1, so Aq_1 = \lambda_1 q_1 and \lVert q_1 \rVert = 1. Extend \{q_1\} to an orthonormal basis \{q_1, q_2, \dots, q_n\} of \mathbb{R}^n (extend to any basis and apply Gram–Schmidt, which leaves q_1 fixed since it is already a unit vector orthogonal to nothing else yet chosen), and let P be the orthogonal matrix with these vectors as columns.

The subspace W = \operatorname{span}(q_2,\dots,q_n) = q_1^\perp is invariant under A: for w \in W, (Aw)\cdot q_1 = w \cdot (Aq_1) = w \cdot (\lambda_1 q_1) = \lambda_1(w\cdot q_1) = 0, using symmetry in the first step exactly as above, so Aw is again orthogonal to q_1, i.e. Aw \in W. Consequently P^{\mathsf T}AP has the block form P^{\mathsf T}AP = \begin{bmatrix} \lambda_1 & 0 \\ 0 & A_1 \end{bmatrix} for some symmetric (n-1)\times(n-1) matrix A_1: the first column of P^{\mathsf T}AP is P^{\mathsf T}(Aq_1) = P^{\mathsf T}(\lambda_1 q_1) = \lambda_1 e_1 (since P^{\mathsf T}q_1 = e_1, q_1 being the first column of the orthogonal matrix P), giving the zero block below \lambda_1; and P^{\mathsf T}AP is symmetric because A is, which forces the zero block to the right of \lambda_1 as well. By the inductive hypothesis, A_1 = Q_1D_1Q_1^{\mathsf T} for some orthogonal (n-1)\times(n-1) matrix Q_1 and diagonal D_1. Setting Q = P\begin{bmatrix} 1 & 0 \\ 0 & Q_1 \end{bmatrix}, \qquad D = \begin{bmatrix} \lambda_1 & 0 \\ 0 & D_1 \end{bmatrix}, the block-diagonal factor is orthogonal (its columns are orthonormal, being e_1 together with the orthonormal columns of Q_1), so Q is a product of orthogonal matrices and hence orthogonal itself. Unwinding the block product, Q^{\mathsf T}AQ = \begin{bmatrix} 1 & 0 \\ 0 & Q_1^{\mathsf T} \end{bmatrix}P^{\mathsf T}AP\begin{bmatrix} 1 & 0 \\ 0 & Q_1 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & Q_1^{\mathsf T} \end{bmatrix}\begin{bmatrix} \lambda_1 & 0 \\ 0 & A_1 \end{bmatrix}\begin{bmatrix} 1 & 0 \\ 0 & Q_1 \end{bmatrix} = \begin{bmatrix} \lambda_1 & 0 \\ 0 & Q_1^{\mathsf T}A_1Q_1 \end{bmatrix} = D, so A = QDQ^{\mathsf T} with Q orthogonal and D diagonal, completing the induction.

Sanity check: take the symmetric matrix A = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}. Its characteristic equation is (2-\lambda)^2 - 1 = 0, so \lambda_1 = 3 and \lambda_2 = 1 — both real, as guaranteed. Solving (A-3I)v=0 gives v_1 = (1,1), and (A-I)v=0 gives v_2 = (1,-1); these two are orthogonal (v_1 \cdot v_2 = 1 - 1 = 0), exactly as the theorem predicts for eigenvectors of distinct eigenvalues. Normalizing gives q_1 = \frac{1}{\sqrt2}(1,1) and q_2 = \frac{1}{\sqrt2}(1,-1), and setting Q = \begin{bmatrix} 1/\sqrt2 & 1/\sqrt2 \\ 1/\sqrt2 & -1/\sqrt2 \end{bmatrix}, D = \begin{bmatrix} 3 & 0 \\ 0 & 1 \end{bmatrix}, a direct multiplication confirms QDQ^{\mathsf T} = A.

(\Leftarrow) Diagonal relative to an orthonormal basis forces normal. If T's matrix is diagonal relative to an orthonormal basis, T^{*}'s matrix relative to the SAME basis is the conjugate transpose of a diagonal matrix — also diagonal. Two diagonal matrices always commute (multiplying entrywise in either order gives the same product), so TT^{*}=T^{*}T.

(\Rightarrow) Normal forces an orthonormal eigenbasis. By Schur's theorem, T's matrix relative to some orthonormal basis \{\mathbf e_1,\dots,\mathbf e_n\} is upper triangular: Te_j = \sum_{i\le j} A_{ij}\mathbf e_i. The proof shows every off-diagonal entry A_{ij} (i<j) must actually be zero, by strong induction on the column index, using that normality forces \lVert T\mathbf e_j\rVert = \lVert T^{*}\mathbf e_j\rVert for every basis vector (a direct consequence of \langle TT^{*}\mathbf e_j,\mathbf e_j\rangle = \langle T^{*}T\mathbf e_j,\mathbf e_j\rangle, i.e. \lVert T^{*}\mathbf e_j\rVert^2 = \lVert T\mathbf e_j\rVert^2). Comparing these two norms column by column, starting from j=1, forces each successive off-diagonal entry above the diagonal to vanish, leaving T's matrix diagonal in this same orthonormal basis. \blacksquare

By the primary decomposition theorem, V = \bigoplus_iG_{\lambda_i}, so it suffices to find a Jordan basis for T restricted to each generalized eigenspace G_{\lambda_i} separately. On G_{\lambda_i}, N = T - \lambda_iI is nilpotent (every vector is killed by some power of N, by definition of the generalized eigenspace), so it suffices to show every nilpotent operator has a Jordan basis (with \lambda=0).

Induct on \dim V. If N=0, every basis is already a union of size-1 Jordan chains. Otherwise, let k be the smallest power with N^k=0, and pick \mathbf v with N^{k-1}\mathbf v \ne \mathbf 0. The chain \mathbf v, N\mathbf v,\dots,N^{k-1}\mathbf v is linearly independent (a dependency relation, applied N^{k-1} times, would force the leading coefficient to vanish against N^{k-1}\mathbf v \ne \mathbf 0, then inductively every coefficient). Let U = \text{span} of this chain — N-invariant, giving a single Jordan block of size k on U.

For the inductive step, N induces an operator \overline N on V/U (well-defined since U is N-invariant), still nilpotent, on a smaller space. By induction, V/U has a Jordan basis for \overline N. Lifting each chain from V/U back to V (choosing a preimage for each coset representative and extending each lifted chain by applying N) produces chains in V that, together with U's own chain, span V — a short but technical linear-algebra argument confirms independence survives the lift, using that U = \ker(N^{k-1}) \cap \text{im}(N^{k-1})-type intersections stay controlled at each step. The resulting basis, organized chain by chain, gives N's matrix as a block-diagonal union of Jordan blocks (with eigenvalue 0); adding back \lambda_iI restores the original T restricted to G_{\lambda_i}, with eigenvalue \lambda_i on each block. \blacksquare

For i=1,\dots,m, let q_i(x) = m_T(x)/(x-\lambda_i)^{d_i} — the minimal polynomial with the i-th factor removed. The polynomials q_1,\dots,q_m have no common root (each root of m_T is missing from exactly one q_i), so they're coprime as a set; by the polynomial version of Bézout's identity, there exist polynomials r_1,\dots,r_m with \sum_i r_i(x)q_i(x) = 1.

Substituting T: \sum_i r_i(T)q_i(T) = I. Define P_i = r_i(T)q_i(T), so \sum_iP_i = I. Each P_i maps V into G_{\lambda_i}: for any \mathbf v, (T-\lambda_iI)^{d_i}P_i\mathbf v = r_i(T)\big[(T-\lambda_iI)^{d_i}q_i(T)\big]\mathbf v = r_i(T)m_T(T) \mathbf v = \mathbf 0, since (T-\lambda_iI)^{d_i}q_i(x) = m_T(x) by construction and m_T(T)=0.

So every \mathbf v = \sum_i P_i\mathbf v is a sum of vectors from the generalized eigenspaces — V = \sum_iG_{\lambda_i}. For the sum to be DIRECT, suppose \sum_i\mathbf w_i = \mathbf 0 with \mathbf w_i\in G_{\lambda_i}. Applying P_j to both sides: for i\ne j, q_j contains the factor (x-\lambda_i)^{d_i} (since i\ne j means (x-\lambda_i)^{d_i} divides q_j), so q_j(T)\mathbf w_i = \mathbf 0 for \mathbf w_i \in G_{\lambda_i}, giving P_j\mathbf w_i = \mathbf 0 for i \ne j. So P_j\big(\sum_i\mathbf w_i\big) = P_j\mathbf w_j, and since the left side is P_j(\mathbf 0)=\mathbf 0, this forces \mathbf w_j = P_j\mathbf w_j = \mathbf 0 (using that P_j acts as the identity on G_{\lambda_j} itself, a direct consequence of \sum_iP_i=I applied within G_{\lambda_j}). Every \mathbf w_j is forced to zero, confirming directness. T-invariance of each G_{\lambda_i} follows since T commutes with (T-\lambda_iI)^{d_i}. \blacksquare

Work relative to a Jordan basis for T (chapter 07's existence theorem), so T's matrix is block-diagonal with Jordan blocks J_{k_1}(\lambda_1),\dots,J_{k_r}(\lambda_r). Since p_T(x) = \prod_i(x-\lambda_i)^{m_i} where m_i is \lambda_i's algebraic multiplicity (the sum of the sizes of all blocks for that eigenvalue), and p_T(T) acts block by block (a polynomial in a block-diagonal matrix is block-diagonal, with the same polynomial applied to each block independently), it suffices to show p_T annihilates each individual Jordan block.

For a block J_k(\lambda_i), the factor (x-\lambda_i)^{m_i} appears in p_T(x) with exponent m_i \ge k (since k is at most the total size m_i of all blocks for \lambda_i combined). Evaluating at T=J_k(\lambda_i): (J_k(\lambda_i)-\lambda_iI) is the nilpotent shift matrix (1s on the superdiagonal, zero elsewhere), and this specific k\times k nilpotent matrix satisfies N^k = 0 exactly (shifting k times off a k-dimensional space lands outside it). Since m_i \ge k, (J_k(\lambda_i)-\lambda_iI)^{m_i} = N^{m_i} = 0 too (a higher power of an already-zero-achieving nilpotent matrix stays zero). So p_T's (x-\lambda_i)^{m_i} factor alone already kills this block, and every OTHER factor in p_T is just being multiplied in afterward, preserving the zero. Since every block is killed, the full block-diagonal p_T(T) is the zero matrix. \blacksquare

A^{\mathsf T}A is an n\times n symmetric matrix, so the real spectral theorem gives an orthonormal eigenbasis \{\mathbf v_1,\dots,\mathbf v_n\} of \mathbb R^n with A^{\mathsf T}A\mathbf v_i = \lambda_i\mathbf v_i. Every eigenvalue is nonnegative: \lambda_i \lVert\mathbf v_i\rVert^2 = \mathbf v_i^{\mathsf T}A^{\mathsf T}A\mathbf v_i = \lVert A\mathbf v_i\rVert^2 \ge 0. Order them so \lambda_1\ge \cdots\ge\lambda_n\ge0 and set \sigma_i = \sqrt{\lambda_i}.

Let r = \text{rank}(A) (equivalently, the number of nonzero \lambda_i, since A\mathbf v_i=\mathbf 0 exactly when \lambda_i=0). For i\le r, define \mathbf u_i = \frac{1}{\sigma_i}A\mathbf v_i. These are orthonormal: \mathbf u_i \cdot \mathbf u_j = \frac{1}{\sigma_i\sigma_j}(A\mathbf v_i)^{\mathsf T}(A\mathbf v_j) = \frac{1}{\sigma_i\sigma_j}\mathbf v_i^{\mathsf T}A^{\mathsf T}A\mathbf v_j = \frac{\lambda_j}{\sigma_i\sigma_j}\mathbf v_i\cdot\mathbf v_j, which is 1 when i=j (since \lambda_i=\sigma_i^2) and 0 otherwise (orthonormality of the \mathbf v_i). Extend \{\mathbf u_1,\dots,\mathbf u_r\} to a full orthonormal basis \{\mathbf u_1,\dots,\mathbf u_m\} of \mathbb R^m (possible since any orthonormal set extends to a full orthonormal basis).

Let V have columns \mathbf v_1,\dots,\mathbf v_n and U have columns \mathbf u_1,\dots,\mathbf u_m — both orthogonal by construction. By definition A\mathbf v_i = \sigma_i\mathbf u_i for i\le r, and A\mathbf v_i=\mathbf 0=\sigma_i\mathbf u_i (since \sigma_i=0) for i>r — so AV = U\Sigma for the matrix \Sigma with \sigma_i down its diagonal. Since V is orthogonal, V^{-1} = V^{\mathsf T}, giving A = U\Sigma V^{\mathsf T} exactly. \blacksquare

First, \lVert A-A_k\rVert_2 = \sigma_{k+1} directly: A-A_k = \sum_{i=k+1}^r\sigma_iu_iv_i^{\mathsf T} is itself a valid SVD (its own terms are still built from orthonormal u_i,v_i), so its largest singular value — which IS its operator norm — is \sigma_{k+1}, the largest of the remaining terms.

For optimality, let B be any matrix with \text{rank}(B)\le k, so \ker(B) has dimension at least n-k (rank-nullity theorem). Let W = \text{span}\{v_1,\dots,v_{k+1}\}, of dimension k+1. Since \dim(\ker B) + \dim(W) \ge (n-k)+(k+1) = n+1 > n, these two subspaces of \mathbb R^n must intersect nontrivially (chapter 01's dimension formula for a sum of subspaces) — pick a unit vector \mathbf w in \ker(B)\cap W.

Since \mathbf w\in\ker(B), (A-B)\mathbf w = A\mathbf w - \mathbf 0 = A\mathbf w. Since \mathbf w\in W, write \mathbf w = \sum_{i=1}^{k+1}c_iv_i with \sum c_i^2=1 (unit vector, orthonormal v_i); then A\mathbf w = \sum_{i=1}^{k+1}c_i\sigma_iu_i, and since the u_i are orthonormal, \lVert A\mathbf w\rVert^2 = \sum_{i=1}^{k+1}c_i^2\sigma_i^2 \ge \sigma_{k+1}^2\sum_{i=1}^{k+1}c_i^2 = \sigma_{k+1}^2 (every \sigma_i\ge\sigma_{k+1} for i\le k+1).

So \lVert A-B\rVert_2 \ge \lVert(A-B)\mathbf w\rVert = \lVert A\mathbf w\rVert \ge \sigma_{k+1} = \lVert A-A_k\rVert_2, proving the operator-norm case — no rank-k matrix B can beat A_k's own operator-norm error. \blacksquare

(\Leftarrow) Orthogonal diagonalizability forces symmetry. Suppose A = QDQ^{\mathsf T} with Q orthogonal and D diagonal. Diagonal matrices equal their own transpose, and transposing a product reverses the order of its factors, so A^{\mathsf T} = (QDQ^{\mathsf T})^{\mathsf T} = (Q^{\mathsf T})^{\mathsf T}D^{\mathsf T}Q^{\mathsf T} = QDQ^{\mathsf T} = A. So A is symmetric. The rest of the proof handles the harder direction.

Symmetric matrices have only real eigenvalues. Let \lambda be an eigenvalue of A, allowing for the moment that it might be complex, with eigenvector v (possibly with complex entries), so Av = \lambda v. Let \bar v denote the entrywise complex conjugate of v, and consider the scalar \bar v^{\mathsf T} A v. Computing it one way, \bar v^{\mathsf T} A v = \bar v^{\mathsf T}(\lambda v) = \lambda (\bar v^{\mathsf T} v) = \lambda \lVert v \rVert^2, since \bar v^{\mathsf T} v = \sum_i \overline{v_i} v_i = \sum_i |v_i|^2 = \lVert v \rVert^2 is real and positive (v \neq 0, being an eigenvector). Computing the same scalar the other way, using A^{\mathsf T} = A and that \bar v^{\mathsf T} A v is a 1\times 1 matrix and so equal to its own transpose, \bar v^{\mathsf T} A v = \left(\bar v^{\mathsf T} A v\right)^{\mathsf T} = v^{\mathsf T} A^{\mathsf T} \bar v = v^{\mathsf T} A \bar v. Taking the complex conjugate of Av = \lambda v gives A\bar v = \bar\lambda \bar v (since A has real entries, conjugation passes through it untouched), so v^{\mathsf T} A \bar v = v^{\mathsf T}(\bar\lambda \bar v) = \bar\lambda (v^{\mathsf T}\bar v) = \bar\lambda \lVert v\rVert^2, using v^{\mathsf T}\bar v = \overline{\bar v^{\mathsf T} v} = \lVert v\rVert^2 again. The two computations of \bar v^{\mathsf T} A v must agree: \lambda \lVert v \rVert^2 = \bar\lambda \lVert v \rVert^2. Since \lVert v \rVert^2 \neq 0, this forces \lambda = \bar\lambda, i.e. \lambda is real. So every eigenvalue of A is real, and consequently every eigenvalue has a real eigenvector (a real matrix minus a real multiple of I_n has a real null space).

Eigenvectors for distinct eigenvalues are orthogonal. Let Av_1 = \lambda_1 v_1 and Av_2 = \lambda_2 v_2 with \lambda_1 \neq \lambda_2. Using symmetry, \lambda_1 (v_1 \cdot v_2) = (Av_1) \cdot v_2 = v_1^{\mathsf T}A^{\mathsf T} v_2 = v_1^{\mathsf T}Av_2 = v_1 \cdot (Av_2) = \lambda_2(v_1 \cdot v_2). So (\lambda_1 - \lambda_2)(v_1 \cdot v_2) = 0, and since \lambda_1 \neq \lambda_2, this forces v_1 \cdot v_2 = 0.

Building Q by induction on n. The base case n=1 is trivial: any 1\times 1 matrix is already diagonal, and Q = [1] is orthogonal. For the inductive step, assume every symmetric (n-1)\times(n-1) matrix is orthogonally diagonalizable, and let A be a symmetric n \times n matrix. By the real-eigenvalue fact above, A has a real eigenvalue \lambda_1 with a real, nonzero eigenvector; rescale it to a unit vector q_1, so Aq_1 = \lambda_1 q_1 and \lVert q_1 \rVert = 1. Extend \{q_1\} to an orthonormal basis \{q_1, q_2, \dots, q_n\} of \mathbb{R}^n (extend to any basis and apply Gram–Schmidt, which leaves q_1 fixed since it is already a unit vector orthogonal to nothing else yet chosen), and let P be the orthogonal matrix with these vectors as columns.

The subspace W = \operatorname{span}(q_2,\dots,q_n) = q_1^\perp is invariant under A: for w \in W, (Aw)\cdot q_1 = w \cdot (Aq_1) = w \cdot (\lambda_1 q_1) = \lambda_1(w\cdot q_1) = 0, using symmetry in the first step exactly as above, so Aw is again orthogonal to q_1, i.e. Aw \in W. Consequently P^{\mathsf T}AP has the block form P^{\mathsf T}AP = \begin{bmatrix} \lambda_1 & 0 \\ 0 & A_1 \end{bmatrix} for some symmetric (n-1)\times(n-1) matrix A_1: the first column of P^{\mathsf T}AP is P^{\mathsf T}(Aq_1) = P^{\mathsf T}(\lambda_1 q_1) = \lambda_1 e_1 (since P^{\mathsf T}q_1 = e_1, q_1 being the first column of the orthogonal matrix P), giving the zero block below \lambda_1; and P^{\mathsf T}AP is symmetric because A is, which forces the zero block to the right of \lambda_1 as well. By the inductive hypothesis, A_1 = Q_1D_1Q_1^{\mathsf T} for some orthogonal (n-1)\times(n-1) matrix Q_1 and diagonal D_1. Setting Q = P\begin{bmatrix} 1 & 0 \\ 0 & Q_1 \end{bmatrix}, \qquad D = \begin{bmatrix} \lambda_1 & 0 \\ 0 & D_1 \end{bmatrix}, the block-diagonal factor is orthogonal (its columns are orthonormal, being e_1 together with the orthonormal columns of Q_1), so Q is a product of orthogonal matrices and hence orthogonal itself. Unwinding the block product, Q^{\mathsf T}AQ = \begin{bmatrix} 1 & 0 \\ 0 & Q_1^{\mathsf T} \end{bmatrix}P^{\mathsf T}AP\begin{bmatrix} 1 & 0 \\ 0 & Q_1 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & Q_1^{\mathsf T} \end{bmatrix}\begin{bmatrix} \lambda_1 & 0 \\ 0 & A_1 \end{bmatrix}\begin{bmatrix} 1 & 0 \\ 0 & Q_1 \end{bmatrix} = \begin{bmatrix} \lambda_1 & 0 \\ 0 & Q_1^{\mathsf T}A_1Q_1 \end{bmatrix} = D, so A = QDQ^{\mathsf T} with Q orthogonal and D diagonal, completing the induction.

Sanity check: take the symmetric matrix A = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}. Its characteristic equation is (2-\lambda)^2 - 1 = 0, so \lambda_1 = 3 and \lambda_2 = 1 — both real, as guaranteed. Solving (A-3I)v=0 gives v_1 = (1,1), and (A-I)v=0 gives v_2 = (1,-1); these two are orthogonal (v_1 \cdot v_2 = 1 - 1 = 0), exactly as the theorem predicts for eigenvectors of distinct eigenvalues. Normalizing gives q_1 = \frac{1}{\sqrt2}(1,1) and q_2 = \frac{1}{\sqrt2}(1,-1), and setting Q = \begin{bmatrix} 1/\sqrt2 & 1/\sqrt2 \\ 1/\sqrt2 & -1/\sqrt2 \end{bmatrix}, D = \begin{bmatrix} 3 & 0 \\ 0 & 1 \end{bmatrix}, a direct multiplication confirms QDQ^{\mathsf T} = A.

Suppose a form Q diagonalizes as \sum_{i=1}^{p} x_i^2 - \sum_{i=p+1}^{p+q} x_i^2 in coordinates (x_1,\dots,x_n) (basis \{e_i\}) and also as \sum_{i=1}^{p'} y_i^2 - \sum_{i=p'+1}^{p'+q'} y_i^2 in coordinates (y_1,\dots,y_n) (basis \{f_i\}). Suppose toward contradiction p \ne p'; WLOG p > p'.

Let P = \operatorname{span}\{e_1,\dots,e_p\} (dimension p, where Q is positive on every nonzero vector) and let N' = \operatorname{span}\{f_{p'+1},\dots,f_n\} (dimension n-p', where Q is negative semidefinite). Since p + (n-p') > n (using p > p'), the dimension formula forces P \cap N' \ne \{\mathbf 0\} — pick a nonzero \mathbf v in that intersection.

Being in P, \mathbf v \ne \mathbf 0 gives Q(\mathbf v) > 0. Being in N', Q(\mathbf v) \le 0. These contradict each other, so the assumption p > p' is false. By symmetry p' > p is also false, forcing p = p'. An identical argument (swapping the roles of positive and negative) gives q = q', and since n_0 = n - p - q is then also determined, the full signature (n_+,n_-,n_0) = (p,q,n_0) is the same for both diagonalizations. \blacksquare

By the real spectral theorem, A has an orthonormal eigenbasis v_1,\dots,v_n with Av_i=\lambda_i v_i. Write x=\sum_i c_i v_i in this basis. Then x^{\mathsf T}Ax = \Big(\sum_i c_iv_i\Big)^{\mathsf T}\Big(\sum_j \lambda_jc_jv_j\Big) = \sum_{i,j}c_ic_j\lambda_j\langle v_i,v_j\rangle = \sum_i \lambda_ic_i^2, using orthonormality to collapse the double sum to i=j. The same computation with A replaced by the identity gives x^{\mathsf T}x=\sum_i c_i^2. So R_A(x) = \frac{\sum_i \lambda_ic_i^2}{\sum_i c_i^2}. This is a weighted average of the eigenvalues \lambda_1,\dots,\lambda_n with nonnegative weights c_i^2/\sum_j c_j^2 summing to 1. A weighted average can never exceed the largest term being averaged nor fall below the smallest, so \lambda_{\min}\le R_A(x)\le\lambda_{\max}.

For the achievability of the bounds: if x=v_1 (the eigenvector for \lambda_{\max}), then c_1=1 and every other c_i=0, so R_A(x) = \lambda_1\cdot 1 = \lambda_{\max} exactly. The identical argument with x=v_n gives R_A(x)=\lambda_{\min}. \blacksquare

Fix an orthonormal eigenbasis v_1,\dots,v_n with Av_i=\lambda_iv_i. For x=\sum_i c_iv_i, the same computation the Rayleigh-Ritz theorem uses gives R_A(x)=\dfrac{\sum_i\lambda_ic_i^2}{\sum_i c_i^2}, a weighted average of the eigenvalues with nonnegative weights summing to 1.

The max-min form. Take S^\ast=\operatorname{span}(v_1,\dots,v_k), which has dimension k. For any nonzero x\in S^\ast, R_A(x) is a weighted average of only \lambda_1,\dots,\lambda_k, all of which are \ge\lambda_k, so R_A(x)\ge\lambda_k for every such x — with equality exactly at x=v_k. So \min_{x\in S^\ast}R_A(x)=\lambda_k, which shows \max_{\dim S=k}\ \min_{x\in S}R_A(x)\ \ge\ \lambda_k. For the reverse inequality, let S be any k-dimensional subspace and set W=\operatorname{span}(v_k,\dots,v_n), which has dimension n-k+1. Since \dim S+\dim W = k+(n-k+1) = n+1 > n, the two subspaces must intersect nontrivially (the same dimension-counting argument the Eckart-Young theorem's own proof uses) — pick a nonzero x\in S\cap W. Because x\in W, R_A(x) is a weighted average of only \lambda_k,\dots,\lambda_n, all of which are \le\lambda_k, so R_A(x)\le\lambda_k. Since x\in S too, \min_{y\in S}R_A(y)\le R_A(x)\le\lambda_k. This holds for every k-dimensional S, so \max_{\dim S=k}\ \min_{x\in S}R_A(x)\ \le\ \lambda_k. Combining both inequalities proves the max-min form.

The min-max form. Take S^\ast=\operatorname{span}(v_k,\dots,v_n), dimension n-k+1. Every nonzero x\in S^\ast has R_A(x) a weighted average of \lambda_k,\dots,\lambda_n, all \le\lambda_k, with equality at x=v_k, so \max_{x\in S^\ast}R_A(x)=\lambda_k, giving \min_{\dim S=n-k+1}\ \max_{x\in S}R_A(x)\ \le\ \lambda_k. For the reverse, let S be any (n-k+1)-dimensional subspace and set W=\operatorname{span}(v_1,\dots,v_k), dimension k. Since \dim S+\dim W = (n-k+1)+k=n+1>n, they intersect nontrivially — pick a nonzero x\in S\cap W. Because x\in W, R_A(x) is a weighted average of \lambda_1,\dots,\lambda_k, all \ge\lambda_k, so R_A(x)\ge\lambda_k, hence \max_{y\in S}R_A(y)\ge\lambda_k. This holds for every such S, so \min_{\dim S=n-k+1}\ \max_{x\in S}R_A(x)\ \ge\ \lambda_k. Combining both inequalities proves the min-max form. \blacksquare

Interlacing. Let W be the coordinate hyperplane \{x\in\mathbb R^n : x_i=0\}, a subspace of dimension n-1. For x\in W, write x'\in\mathbb R^{n-1} for x with its (zero) i-th coordinate dropped. Since x_i=0, every term in x^{\mathsf T}Ax involving row or column i of A vanishes, leaving exactly x'^{\mathsf T}Bx'; and x^{\mathsf T}x=x'^{\mathsf T}x' for the same reason. So R_A(x)=R_B(x') for every x\in W, and this correspondence x\leftrightarrow x' is a bijection between subspaces of W and subspaces of \mathbb R^{n-1} that preserves dimension.

By the Courant-Fischer max-min form applied to B, \mu_k = \max_{\substack{S'\subseteq\mathbb R^{n-1}\\ \dim S'=k}}\ \min_{x'\in S'} R_B(x') = \max_{\substack{S\subseteq W\\ \dim S=k}}\ \min_{x\in S} R_A(x), using the correspondence just established. The right side is a maximum over only those k-dimensional subspaces contained in W — a restricted class compared to the maximum over every k-dimensional subspace of \mathbb R^n that defines \lambda_k via Courant-Fischer. Restricting the subspaces a maximum ranges over can only lower (or leave unchanged) the maximum, so \mu_k\le\lambda_k.

For the other bound, apply the Courant-Fischer min-max form to B at index k (using dimension (n-1)-k+1=n-k) and to A at index k+1 (using dimension n-(k+1)+1=n-k — the same dimension): \mu_k = \min_{\substack{S'\subseteq\mathbb R^{n-1}\\ \dim S'=n-k}}\ \max_{x'\in S'} R_B(x') = \min_{\substack{S\subseteq W\\ \dim S=n-k}}\ \max_{x\in S} R_A(x),\qquad \lambda_{k+1} = \min_{\substack{S\subseteq\mathbb R^n\\ \dim S=n-k}}\ \max_{x\in S} R_A(x). Now \mu_k minimizes over the restricted class of (n-k)-dimensional subspaces lying inside W, while \lambda_{k+1} minimizes over every (n-k)-dimensional subspace of \mathbb R^n. Restricting the subspaces a minimum ranges over can only raise (or leave unchanged) the minimum, so \mu_k\ge\lambda_{k+1}. Combining both bounds proves \lambda_{k+1}\le\mu_k\le\lambda_k.

Weyl's inequality. For any nonzero x, R_{A+B}(x) = \dfrac{x^{\mathsf T}(A+B)x}{x^{\mathsf T}x} = R_A(x)+R_B(x), since the quadratic form of a sum is the sum of the quadratic forms. By the Rayleigh-Ritz theorem, \lambda_n(B)\le R_B(x)\le\lambda_1(B) for every nonzero x.

For the lower bound, fix any subspace S of dimension i. For every x\in S, R_{A+B}(x) = R_A(x)+R_B(x)\ge R_A(x)+\lambda_n(B), so \min_{x\in S}R_{A+B}(x)\ge\min_{x\in S}R_A(x)+\lambda_n(B). Taking the maximum of both sides over all i-dimensional S and applying the Courant-Fischer max-min form to both A+B and A, \lambda_i(A+B) = \max_{\dim S=i}\min_{x\in S}R_{A+B}(x) \ge \max_{\dim S=i}\min_{x\in S}R_A(x) + \lambda_n(B) = \lambda_i(A)+\lambda_n(B).

For the upper bound, the identical argument with R_{A+B}(x)\le R_A(x)+\lambda_1(B) for every x gives, after taking the maximum over i-dimensional S, \lambda_i(A+B) \le \lambda_i(A) + \lambda_1(B). Combining both bounds proves the inequality. \blacksquare

This proof covers the DIAGONALIZABLE case; a non-diagonalizable matrix needs the Jordan canonical form in place of an eigenvector basis, with the identical conclusion, but the bookkeeping is heavier and is not carried out here.

Write A=VDV^{-1} with D=\operatorname{diag}(\lambda_1,\dots,\lambda_n) and V's columns the eigenvectors. Order so |\lambda_1|=\rho(A).

Lower bound. Since Av_1=\lambda_1v_1, A^nv_1=\lambda_1^nv_1, so \lVert A^n\rVert \ge \frac{\lVert A^nv_1\rVert}{\lVert v_1\rVert} = |\lambda_1|^n = \rho(A)^n, using the operator norm's own definition as a maximum over ALL unit vectors, hence in particular at least as large as its value at v_1/\lVert v_1\rVert. Taking n-th roots, \lVert A^n\rVert^{1/n} \ge \rho(A) for every n.

Upper bound. A^n = VD^nV^{-1}, so by submultiplicativity, \lVert A^n\rVert \le \lVert V\rVert\,\lVert D^n\rVert\,\lVert V^{-1}\rVert. Since D is diagonal, \lVert D^n\rVert = \max_i|\lambda_i|^n = \rho(A)^n exactly (the induced 2-norm of a diagonal matrix is its largest diagonal-entry magnitude). So \lVert A^n\rVert^{1/n} \le \big(\lVert V\rVert\,\lVert V^{-1}\rVert\big)^{1/n}\cdot\rho(A). The constant \kappa=\lVert V\rVert\,\lVert V^{-1}\rVert does not depend on n, and \kappa^{1/n}\to 1 as n\to\infty (any fixed positive constant raised to the power 1/n converges to 1). So the upper bound converges to \rho(A).

Combining. For every n, \rho(A) \le \lVert A^n\rVert^{1/n} \le \kappa^{1/n}\rho(A), and the right side converges to \rho(A) as n\to\infty. By the squeeze theorem, \lVert A^n\rVert^{1/n}\to \rho(A). \blacksquare

Let S_n = I+A+A^2+\cdots+A^n be the n-th partial sum. Multiplying by I-A telescopes: (I-A)S_n = S_n - AS_n = (I+A+\cdots+A^n) - (A+A^2+\cdots+A^{n+1}) = I - A^{n+1}. Since \rho(A)<1, the equivalence proved alongside Gelfand's formula gives A^{n+1}\to 0 as n\to\infty. Taking the limit of both sides, (I-A)\lim_{n\to\infty}S_n = I - 0 = I, so \lim_{n\to\infty}S_n is a right inverse of I-A; an identical computation with S_n(I-A) shows it is a left inverse too. A square matrix with both a left and a right inverse is invertible with that common inverse, so (I-A)^{-1}=\lim_{n\to\infty}S_n = \sum_{k=0}^\infty A^k. \blacksquare

Let \mu be an eigenvalue of A+E with eigenvector x, (A+E)x=\mu x. If \mu already equals some \lambda_i, the bound holds trivially. Otherwise \mu I - A is invertible, and rearranging (A+E)x=\mu x gives (\mu I-A)x = Ex, so x = (\mu I-A)^{-1}Ex. Taking norms, \lVert x\rVert \le \lVert(\mu I-A)^{-1}\rVert\,\lVert E\rVert\,\lVert x\rVert, and since x\ne 0, 1 \le \lVert(\mu I-A)^{-1}\rVert\,\lVert E\rVert. Writing \mu I - A = V(\mu I-D)V^{-1}, so (\mu I-A)^{-1} = V(\mu I-D)^{-1}V^{-1}, submultiplicativity gives \lVert(\mu I-A)^{-1}\rVert \le \lVert V\rVert\,\lVert(\mu I-D)^{-1}\rVert\,\lVert V^{-1}\rVert = \kappa(V)\,\lVert(\mu I-D)^{-1}\rVert. Since \mu I-D is diagonal with entries \mu-\lambda_i, \lVert(\mu I-D)^{-1}\rVert = \max_i \frac{1}{|\mu-\lambda_i|} = \frac{1}{\min_i|\mu-\lambda_i|}. Substituting, 1 \le \kappa(V)\cdot\frac{\lVert E\rVert}{\min_i|\mu-\lambda_i|}, which rearranges directly to \min_i|\mu-\lambda_i| \le \kappa(V)\,\lVert E\rVert. \blacksquare

Let \{e_i\}_{i=1}^n be a basis of V and \{f_j\}_{j=1}^m a basis of W. Define V\otimes W to be the vector space with basis the nm symbols \{e_i\otimes f_j\}, and extend \otimes to all of V\times W bilinearly: for v=\sum_ic_ie_i, w=\sum_jd_jf_j, set v\otimes w := \sum_{i,j} c_id_j\,(e_i\otimes f_j). This is bilinear in v,w by direct computation from the definition.

Existence of \widetilde B. Given any bilinear B, define \widetilde B on the basis by \widetilde B(e_i\otimes f_j):=B(e_i,f_j), and extend linearly to all of V\otimes W. For a general v\otimes w=\sum_{i,j}c_id_j(e_i\otimes f_j), \widetilde B(v\otimes w) = \sum_{i,j}c_id_j\,\widetilde B(e_i\otimes f_j) = \sum_{i,j}c_id_j\,B(e_i,f_j) = B\Big(\sum_ic_ie_i,\sum_jd_jf_j\Big)=B(v,w), using bilinearity of B in the last step. So \widetilde B satisfies the required property.

Uniqueness of \widetilde B. Any linear map agreeing with B on every v\otimes w in particular agrees on every basis tensor e_i\otimes f_j — and a linear map is completely determined by its values on a basis. So any two such maps agree everywhere, forcing \widetilde B to be unique. \blacksquare

Write each column A_j=\sum_{i=1}^n a_{ij}e_i. By multilinearity, expanding all n arguments simultaneously, D(A_1,\dots,A_n) = \sum_{i_1,\dots,i_n=1}^n a_{i_1 1}a_{i_2 2}\cdots a_{i_n n}\,D(e_{i_1},\dots,e_{i_n}), a sum over every possible choice of indices i_1,\dots,i_n\in\{1,\dots,n\}.

Whenever two of the chosen indices coincide, say i_k=i_l for k\ne l, the alternating property forces D(e_{i_1},\dots,e_{i_n})=0 (the same vector e_{i_k} appears in two argument slots). So only terms where (i_1,\dots,i_n) is a PERMUTATION of (1,\dots,n) survive — write i_k=\sigma(k) for a permutation \sigma.

For each surviving term, repeatedly swapping arguments to sort (e_{\sigma(1)},\dots,e_{\sigma(n)}) back into (e_1,\dots,e_n) order flips D's sign once per swap (the alternating property), and sorting any permutation takes exactly \operatorname{sgn}(\sigma) many sign flips in total (the standard fact that a permutation's sign counts transpositions mod 2). So D(e_{\sigma(1)},\dots,e_{\sigma(n)}) = \operatorname{sgn}(\sigma)\,D(e_1,\dots,e_n) = \operatorname{sgn}(\sigma), using the normalization D(e_1,\dots,e_n)=1. Substituting back, D(A_1,\dots,A_n) = \sum_{\sigma\in S_n} \operatorname{sgn}(\sigma)\,a_{\sigma(1)1}a_{\sigma(2)2}\cdots a_{\sigma(n)n}, exactly the Leibniz formula for \det A. Since D was an arbitrary function satisfying the three hypotheses, and this computation shows its value is FORCED at every input, D must equal \det exactly — proving both that the determinant satisfies these properties and that it is the unique function that does. \blacksquare