The Grassmann dimension formula

Theorem

The Grassmann dimension formula

T-141Home MU-103Threads structure

Statement

Let \( F \) be a field, let \( V \) be a vector space over \( F \), and let \( U \) and \( W \) be subspaces of \( V \), both finite-dimensional. Then the sum \( U + W = \{ u + w : u \in U,\ w \in W \} \) and the intersection \( U \cap W \) are subspaces of \( V \), both finite-dimensional, and \[ \dim (U + W) \; + \; \dim (U \cap W) \; = \; \dim U \; + \; \dim W . \] No hypothesis is needed on \( V \): it may be infinite-dimensional, and the field \( F \) is arbitrary.

Why it matters

Grassmann's formula is the inclusion–exclusion principle of linear algebra. Two subspaces overlap, and the formula says exactly how much: the dimensions of \( U \) and \( W \) double-count the overlap once, so subtracting \( \dim (U \cap W) \) from \( \dim U + \dim W \) recovers the dimension of the space they jointly span. Every practical question about how subspaces sit inside one another — do two planes in \( \mathbb{R}^4 \) meet in more than the origin? how many solutions do two homogeneous systems share? is a sum direct? — is settled by this one identity, usually without computing the intersection at all.

It is also the reason the geometry of linear subspaces is rigid. In \( \mathbb{R}^3 \) two distinct planes through the origin cannot miss each other: \( 2 + 2 - 3 = 1 \), so they meet in at least a line. In \( \mathbb{R}^5 \) two three-dimensional subspaces always share a line. Rearranged as \( \dim (U \cap W) \ge \dim U + \dim W - \dim V \), the formula is the linear ancestor of every dimension count in intersection theory, from “two lines in the projective plane meet” to the dimension formulae of Schubert calculus. Together with the rank–nullity theorem it accounts for essentially all elementary dimension bookkeeping.

Hypotheses

\( U \) and \( W \) are subspaces of one ambient space \( V \).Both \( U + W \) and \( U \cap W \) must make sense and be subspaces. For affine subspaces (cosets) the statement is false: the two parallel lines \( U = \{ (t, 0) : t \in \mathbb{R} \} \) and \( W = \{ (t, 1) : t \in \mathbb{R} \} \) in \( \mathbb{R}^2 \) are each one-dimensional, their affine hull is two-dimensional, and \( U \cap W = \varnothing \) has no dimension at all.

\( U \) and \( W \) are finite-dimensional.Only then are all four terms finite cardinals that can be added and cancelled. In \( V = \mathbb{R}[x] \) take \( U = W = V \) and then \( U' = \operatorname{span}\{ x^{2n} : n \ge 0 \} \), \( W' = \operatorname{span}\{ x^{2n+1} : n \ge 0 \} \): both pairs have all of \( \dim U, \dim W, \dim (U + W) \) infinite, yet the intersections are \( V \) and \( \{0\} \). The formula degenerates to \( \infty = \infty \) and determines nothing.

One field of scalars throughout.Dimension is dimension over \( F \). Viewing \( \mathbb{C}^2 \) as \( \mathbb{C} \)-space or as \( \mathbb{R} \)-space changes every entry in the identity by a factor of \( 2 \); mixing the two counts in one equation produces nonsense. Fix \( F \) first, then count.

Dimension is well defined, and bases extend.The proof uses that all bases of a finite-dimensional space have the same size (invariance of dimension) and that any independent set in a finite-dimensional space extends to a basis (Steinitz exchange). Over a division ring both still hold; over a general ring neither does, and the “dimension” of a submodule is not even defined — the correct heir there is composition length, not dimension.

Proof

Write \( m = \dim U \), \( n = \dim W \) and \( p = \dim (U \cap W) \). The strategy is the one that works for every such formula: build a basis of the overlap first, then extend it in two directions, and prove that the three blocks together form a basis of the sum. Nothing is chosen twice, so nothing is counted twice.

\( U \cap W \) and \( U + W \) are subspaces of \( V \), and \( U \cap W \subseteq U \subseteq U + W \).

An intersection of subspaces is closed under addition and scalar multiplication because each of \( U \), \( W \) is; for the sum, \( (u_1 + w_1) + \lambda (u_2 + w_2) = (u_1 + \lambda u_2) + (w_1 + \lambda w_2) \) is again of the required shape, and \( 0 = 0 + 0 \) lies in it. The inclusions are immediate from \( u = u + 0 \). A

\( U \cap W \) is finite-dimensional with \( p = \dim (U \cap W) \le m \); choose a basis \( \mathcal{A} = \{ a_1, \dots, a_p \} \) of \( U \cap W \).

Every subspace of a finite-dimensional space is finite-dimensional of no larger dimension, and has a basis; here \( U \cap W \subseteq U \) and \( \dim U = m \). If \( p = 0 \), take \( \mathcal{A} = \varnothing \) — every sum indexed by \( \mathcal{A} \) below is then empty, hence zero, and no step changes. A

Extend \( \mathcal{A} \) inside \( U \) and, separately, inside \( W \): \[ \{ a_1, \dots, a_p, u_1, \dots, u_{m-p} \} \ \text{a basis of } U, \qquad \{ a_1, \dots, a_p, w_1, \dots, w_{n-p} \} \ \text{a basis of } W . \]

Basis extension (Steinitz exchange): an independent subset of a finite-dimensional space extends to a basis of it. The counts \( m - p \) and \( n - p \) are forced because every basis of \( U \) has \( m \) elements and every basis of \( W \) has \( n \) (invariance of dimension). Note that \( \mathcal{A} \) is used as the common starting block of both bases — this is the whole idea of the proof. B

The list \[ \mathcal{B} = \{ a_1, \dots, a_p, \ u_1, \dots, u_{m-p}, \ w_1, \dots, w_{n-p} \} \] spans \( U + W \).

Any element of \( U + W \) is \( u + w \) with \( u \in U \), \( w \in W \). Expand \( u \) in the basis of \( U \) and \( w \) in the basis of \( W \); every vector appearing lies in \( \mathcal{B} \), and the two expansions add. Conversely each member of \( \mathcal{B} \) lies in \( U \) or in \( W \), hence in \( U + W \), so \( \operatorname{span} \mathcal{B} = U + W \). A

\( \mathcal{B} \) is linearly independent. Suppose \[ \sum_{k=1}^{p} \alpha_k a_k \; + \; \sum_{i=1}^{m-p} \beta_i u_i \; + \; \sum_{j=1}^{n-p} \gamma_j w_j \; = \; 0, \qquad \alpha_k, \beta_i, \gamma_j \in F, \] and set \[ x \; = \; \sum_{j=1}^{n-p} \gamma_j w_j \; = \; - \sum_{k=1}^{p} \alpha_k a_k \; - \; \sum_{i=1}^{m-p} \beta_i u_i . \]

The left expression exhibits \( x \) as a combination of vectors of \( W \), so \( x \in W \); the right exhibits the same \( x \) as a combination of vectors of \( U \), so \( x \in U \). Hence \( x \in U \cap W \). This is the pivot of the argument: a relation that mixes the two blocks is forced into the overlap, which is precisely the block we controlled first. C

Since \( x \in U \cap W \) there are \( \delta_k \in F \) with \( x = \sum_{k=1}^{p} \delta_k a_k \), so \[ \sum_{k=1}^{p} \delta_k a_k \; - \; \sum_{j=1}^{n-p} \gamma_j w_j \; = \; 0 \quad \Longrightarrow \quad \delta_1 = \dots = \delta_p = 0, \ \ \gamma_1 = \dots = \gamma_{n-p} = 0 . \]

The first equality is the expansion of \( x \) in the basis \( \mathcal{A} \) of \( U \cap W \); the displayed relation is then a relation among \( a_1, \dots, a_p, w_1, \dots, w_{n-p} \), which is a basis of \( W \) by Step 3, so all its coefficients vanish. In particular every \( \gamma_j = 0 \), and therefore \( x = 0 \). C

With all \( \gamma_j = 0 \) the original relation collapses to \[ \sum_{k=1}^{p} \alpha_k a_k + \sum_{i=1}^{m-p} \beta_i u_i = 0 \quad \Longrightarrow \quad \alpha_k = 0 \ \text{for all } k, \qquad \beta_i = 0 \ \text{for all } i . \]

This is a relation among \( a_1, \dots, a_p, u_1, \dots, u_{m-p} \), a basis of \( U \) by Step 3, so every coefficient vanishes. Combined with Step 6, all \( \alpha, \beta, \gamma \) are zero: \( \mathcal{B} \) is independent. B

\( \mathcal{B} \) is a basis of \( U + W \) with exactly \( p + (m - p) + (n - p) \) members, so \[ \dim (U + W) \; = \; m + n - p \; = \; \dim U + \dim W - \dim (U \cap W) . \]

Spanning (Step 4) plus independence (Steps 5–7) is the definition of a basis; the members are pairwise distinct, since a repetition would be a linear dependence. Adding \( p = \dim (U \cap W) \) to both sides puts the identity in its symmetric form. \( \blacksquare \) A

Result

\[ \dim (U + W) + \dim (U \cap W) = \dim U + \dim W \qquad \text{for subspaces } U, W \text{ of } V \text{ with } \dim U, \dim W \lt \infty . \]

Reading. Counting the dimensions of \( U \) and of \( W \) separately counts the overlap twice; the identity is the correction. Equivalently, \( \dim (U + W) = \dim U + \dim W - \dim (U \cap W) \) — inclusion–exclusion, with dimension in place of cardinality.

Scope. Any field (or division ring), any ambient space \( V \), including infinite-dimensional \( V \); only \( U \) and \( W \) themselves must be finite-dimensional. If \( V \) is finite-dimensional the identity plus \( U + W \subseteq V \) gives the intersection bound \( \dim (U \cap W) \ge \dim U + \dim W - \dim V \). There is no valid three-subspace inclusion–exclusion version; three or more subspaces are handled by iterating the two-subspace identity.

Corollaries & converses

Direct-sum criterion. \( \dim (U + W) = \dim U + \dim W \) exactly when \( U \cap W = \{0\} \), i.e. exactly when the sum is direct, \( U + W = U \oplus W \). Every vector of \( U \oplus W \) then has a unique decomposition \( u + w \).
Intersection bound. If \( \dim V = N \lt \infty \) then \( \dim (U \cap W) \ge \dim U + \dim W - N \). Two planes in \( \mathbb{R}^3 \) meet in at least a line; two \( 3 \)-dimensional subspaces of \( \mathbb{R}^5 \) meet in at least a line; two hyperplanes in \( F^N \) meet in dimension at least \( N - 2 \).
Complements. If \( U \subseteq V \) with \( \dim V = N \lt \infty \), any \( W \) with \( U \cap W = \{0\} \) and \( \dim W = N - \dim U \) satisfies \( U \oplus W = V \). Complements exist and are almost never unique: in \( \mathbb{R}^2 \) every line other than \( U \) itself complements a given line \( U \).
Codimension is additive downwards. Writing \( \operatorname{codim} X = N - \dim X \) in a space of dimension \( N \), the formula reads \( \operatorname{codim}(U \cap W) \le \operatorname{codim} U + \operatorname{codim} W \), with equality precisely when \( U + W = V \) (“\( U \) and \( W \) are transverse”).
Second isomorphism theorem, in dimensions. \( (U + W)/W \cong U/(U \cap W) \) as vector spaces; taking dimensions of both sides and using \( \dim (X/Y) = \dim X - \dim Y \) is exactly Grassmann's formula. The isomorphism is the stronger statement; the formula is its numerical shadow.
Realisability (converse). The identity is the only constraint: given \( N \) and integers \( m, n, p \) with \( 0 \le p \le \min(m,n) \) and \( m + n - p \le N \), there are subspaces of \( F^N \) with \( \dim U = m \), \( \dim W = n \), \( \dim (U \cap W) = p \). Take \( U = \operatorname{span}(e_1, \dots, e_m) \) and \( W = \operatorname{span}(e_{m-p+1}, \dots, e_{m-p+n}) \).
Iterated form. For three subspaces the correct statement is obtained by applying the formula twice: \( \dim (U_1 + U_2 + U_3) = \dim U_1 + \dim U_2 + \dim U_3 - \dim (U_1 \cap U_2) - \dim ((U_1 + U_2) \cap U_3) \). The term \( (U_1 + U_2) \cap U_3 \) cannot be replaced by pairwise and triple intersections.

Fails without

Subspaces replaced by affine subspaces (cosets): in \( \mathbb{R}^3 \) let \( U = \{ (x, y, 0) \} \) and \( W = \{ (x, y, 1) \} \), two parallel planes. Each is a two-dimensional affine subspace, their affine hull is all of \( \mathbb{R}^3 \) (dimension \( 3 \)) and their intersection is empty, so the count reads \( 3 + (\text{nothing}) \ne 2 + 2 \). The proof breaks at the very start: \( U \cap W \) is not a subspace at all, so Step 2 has no basis \( \mathcal{A} \) to build from and there is no common block for Step 3 to extend. Restoring the theorem for affine flats requires the convention \( \dim \varnothing = -1 \) and the projective, not affine, count.
Finite-dimensionality dropped: in \( V = \mathbb{R}[x] \) compare \( (U, W) = (V, V) \), where \( U \cap W = V \) and \( U + W = V \), with \( (U', W') = ( \operatorname{span}\{ x^{2n} \}, \operatorname{span}\{ x^{2n+1} \} ) \), where \( U' \cap W' = \{ 0 \} \) and \( U' + W' = V \). All of \( \dim U, \dim W, \dim (U + W) \) are the same infinite cardinal in both cases, yet the intersections have dimensions \( \aleph_0 \) and \( 0 \). Infinite cardinal arithmetic cannot be cancelled, so the formula carries no information; the useful infinite-dimensional statements are about codimension instead (if \( \operatorname{codim} U \) and \( \operatorname{codim} W \) are finite, then \( \operatorname{codim}(U \cap W) \le \operatorname{codim} U + \operatorname{codim} W \) still holds).
Three subspaces instead of two: inclusion–exclusion does not extend. Take the three distinct lines \( L_1 = \operatorname{span}(1,0) \), \( L_2 = \operatorname{span}(0,1) \), \( L_3 = \operatorname{span}(1,1) \) in \( \mathbb{R}^2 \). All pairwise and triple intersections are \( \{0\} \), so the naive count gives \( 1 + 1 + 1 - 0 - 0 - 0 + 0 = 3 \), while \( \dim (L_1 + L_2 + L_3) = 2 \). The lattice of subspaces is modular but not distributive, and inclusion–exclusion needs distributivity.
Vector spaces replaced by modules over a general ring: over \( R = \mathbb{Z} \) the module \( M = \mathbb{Z}/6\mathbb{Z} \) has submodules \( U = \{0,3\} \) and \( W = \{0,2,4\} \) with \( U \cap W = \{0\} \) and \( U + W = M \); none of \( U \), \( W \), \( M \) is free — each has non-trivial torsion, so no \( \mathbb{Z} \)-basis exists and “dimension” is undefined. The surviving statement replaces dimension by composition length, which is additive in the same way: \( \ell(U + W) + \ell(U \cap W) = \ell(U) + \ell(W) \) — here \( 2 + 0 = 1 + 1 \).

Common errors

“\( \dim (U + W) = \dim U + \dim W \).” True only when the sum is direct. In \( \mathbb{R}^3 \), two distinct planes give \( 2 + 2 = 4 \gt 3 \), which already exceeds the dimension of the ambient space — a useful sanity check that the subtraction has been forgotten.
Confusing \( U + W \) with \( U \cup W \). The union of two distinct lines in \( \mathbb{R}^2 \) is not a subspace (it is not closed under addition); the sum is the subspace it generates. Grassmann's formula is about the sum, and this is exactly why it is not literal inclusion–exclusion on sets.
Extending to three or more subspaces. “\( \dim (U_1 + U_2 + U_3) = \sum \dim U_i - \sum \dim (U_i \cap U_j) + \dim (U_1 \cap U_2 \cap U_3) \)” is false; see the three lines in \( \mathbb{R}^2 \) above. Iterate the two-subspace formula instead.
“Complementary dimensions force trivial intersection.” In \( \mathbb{R}^4 \) two planes with \( 2 + 2 = 4 = \dim V \) may meet in a line, in which case their sum is only three-dimensional. The formula constrains the four numbers; it does not choose them.
Assuming pairwise-trivial intersections make a sum direct. For three or more summands directness needs \( U_i \cap \sum_{j \ne i} U_j = \{0\} \) for each \( i \), which the three lines in \( \mathbb{R}^2 \) fail while meeting pairwise in \( \{0\} \).
Reading “\( \dim (U \cap W) \ge \dim U + \dim W - \dim V \)” as an equality. It is an equality exactly when \( U + W = V \). Two coincident planes in \( \mathbb{R}^3 \) have \( \dim (U \cap W) = 2 \gt 1 \).
Applying it to a subspace and a non-subspace. Solution sets of inhomogeneous systems are affine, not linear; two such sets can be disjoint, and no dimension identity of this kind applies until they are translated back through the origin.

Discussion

The formula is the dimension-theoretic content of the modular law. In the lattice of subspaces of \( V \), ordered by inclusion with meet \( \cap \) and join \( + \), Dedekind's modular law says that \( U \subseteq X \) implies \( X \cap (U + W) = U + (X \cap W) \). Vector-space lattices are always modular and, as the three-line example shows, essentially never distributive when \( \dim V \ge 2 \). Grassmann's formula is what modularity looks like after one applies a “measure” — the dimension — and it is the reason all valid dimension counts come from iterating a two-term identity rather than from a general inclusion–exclusion expansion.

Structurally the cleanest proof is the isomorphism-theoretic one. The inclusion \( U \hookrightarrow U + W \) followed by the quotient map \( U + W \to (U + W)/W \) is surjective with kernel \( U \cap W \), so it induces \( U/(U \cap W) \cong (U + W)/W \); the dimension count then follows from \( \dim (X/Y) = \dim X - \dim Y \), itself a consequence of the rank–nullity theorem. A third route, worked as Problem 5 below, applies rank–nullity directly to the map \( \sigma : U \oplus W \to V \), \( \sigma(u, w) = u - w \), whose image is \( U + W \) and whose kernel is a copy of \( U \cap W \). The basis-building proof given above is the one to keep in the hands, because it produces an explicit basis of \( U + W \) adapted to the intersection — the object one actually needs in computations.

Hermann Grassmann proved the result in his Die lineale Ausdehnungslehre of 1844, decades before vector spaces were axiomatised; the same book introduced the exterior product \( u \wedge w \) that carries his name, and the two ideas are related: \( u \wedge w = 0 \) exactly when the two vectors span a space of dimension less than \( 2 \), which is the smallest case of the formula. In the modern literature the identity is often called simply “the dimension formula” for sums of subspaces, and it is stated for modules of finite length as the additivity of length — the version that survives when scalars stop forming a field.

The geometric descendant is transversality. The set of all \( k \)-dimensional subspaces of \( F^N \) is the Grassmannian \( \operatorname{Gr}(k, N) \), a smooth projective variety of dimension \( k(N - k) \) over an algebraically closed field. For a fixed \( U \) of dimension \( m \), the locus of \( W \in \operatorname{Gr}(n, N) \) with \( \dim (U \cap W) \ge p \) is a Schubert variety of codimension \( p \, (p - m - n + N) \) inside the Grassmannian, so for generic \( W \) the intersection has the smallest dimension the formula permits, namely \( \max(0, \, m + n - N) \), and larger intersections are non-generic degenerations. Grassmann's formula is thus the “expected dimension” statement that intersection theory perturbs everything else towards: excess intersection is measured by how far \( \dim (U \cap W) \) exceeds \( m + n - N \), exactly as the excess of a Schubert cycle is measured against its expected codimension.

Common misconceptions. The formula does not say that \( U + W = U \oplus W \) (it says when); it does not say the intersection is small, only that it cannot be smaller than \( \dim U + \dim W - \dim V \); it says nothing about whether \( U \) and \( W \) are orthogonal, since no inner product appears anywhere in the proof; and the two sides being equal does not mean the four subspaces are related by any canonical splitting — only that the counts balance.

Worked examples

Example 1 (two three-dimensional subspaces of \( \mathbb{R}^5 \)). Let \[ U = \operatorname{span}\{ u_1, u_2, u_3 \}, \quad u_1 = (1,0,1,0,1), \ u_2 = (0,1,0,1,0), \ u_3 = (1,1,0,0,0), \] \[ W = \operatorname{span}\{ w_1, w_2, w_3 \}, \quad w_1 = (1,0,1,1,2), \ w_2 = (0,1,0,0,-1), \ w_3 = (0,1,0,2,1). \] Find \( \dim U \), \( \dim W \), \( \dim (U + W) \) and \( \dim (U \cap W) \), and exhibit a basis of \( U \cap W \).

Row reduce the matrix whose rows are \( u_1, u_2, u_3 \). With \( R_3 \mapsto R_3 - R_1 - R_2 \) and then \( R_3 \mapsto -R_3 \), \[ \begin{pmatrix} 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 \end{pmatrix} \longrightarrow \begin{pmatrix} 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 \end{pmatrix}, \] three pivots (columns \( 1, 2, 3 \)), so \( \dim U = 3 \).

Elementary row operations preserve the row space; the number of pivots in an echelon form is the dimension of that row space. A

Likewise for \( W \): with \( R_3 \mapsto R_3 - R_2 \) and \( R_3 \mapsto \tfrac{1}{2} R_3 \), \[ \begin{pmatrix} 1 & 0 & 1 & 1 & 2 \\ 0 & 1 & 0 & 0 & -1 \\ 0 & 1 & 0 & 2 & 1 \end{pmatrix} \longrightarrow \begin{pmatrix} 1 & 0 & 1 & 1 & 2 \\ 0 & 1 & 0 & 0 & -1 \\ 0 & 0 & 0 & 1 & 1 \end{pmatrix}, \] three pivots (columns \( 1, 2, 4 \)), so \( \dim W = 3 \).

Same justification. The last row shows \( b := (0,0,0,1,1) = \tfrac{1}{2}(w_3 - w_2) \in W \), a fact used in Step 4. A

Stack the two echelon blocks — rows \( A_1 = (1,0,1,0,1) \), \( A_2 = (0,1,0,1,0) \), \( A_3 = (0,0,1,1,1) \) from \( U \) and \( B_1 = (1,0,1,1,2) \), \( B_2 = (0,1,0,0,-1) \), \( B_3 = (0,0,0,1,1) \) from \( W \) — and clear the \( B \) block: \[ B_1 - A_1 = (0,0,0,1,1), \qquad B_2 - A_2 = -(0,0,0,1,1), \qquad B_3 = (0,0,0,1,1). \] All three collapse to the single new row \( (0,0,0,1,1) \), so \[ U + W = \operatorname{span}\{ (1,0,1,0,1), \ (0,1,0,1,0), \ (0,0,1,1,1), \ (0,0,0,1,1) \}, \] four rows with leading entries in columns \( 1, 2, 3, 4 \): \( \dim (U + W) = 4 \).

\( U + W \) is the row space of the stacked matrix, and row operations across the whole stack preserve it; each block may be reduced first because that does not change its own row space. The four surviving rows are in echelon form, hence independent, so the rank is \( 4 \) and not \( 3 \). B

Grassmann's formula now gives the intersection without solving any system: \[ \dim (U \cap W) = \dim U + \dim W - \dim (U + W) = 3 + 3 - 4 = 2 . \] Two independent common vectors are \( u_1 \) and \( u_2 \): with \( b = (0,0,0,1,1) \in W \), \[ w_1 - b = (1,0,1,0,1) = u_1, \qquad w_2 + b = (0,1,0,1,0) = u_2 . \]

The formula supplies the number \( 2 \); the two displayed identities certify membership in \( W \), and \( u_1, u_2 \in U \) by definition. They are independent (look at coordinates \( 1 \) and \( 2 \)), and since the formula says the intersection has dimension exactly \( 2 \), they are a basis of it — no further solutions can have been missed. B

\[ \dim U = 3, \quad \dim W = 3, \quad \dim (U + W) = 4, \quad \dim (U \cap W) = 2, \qquad 4 + 2 = 3 + 3 . \]

Reading. The two subspaces overlap in a plane, \( U \cap W = \operatorname{span}\{ (1,0,1,0,1), (0,1,0,1,0) \} \), and jointly span a four-dimensional subspace of \( \mathbb{R}^5 \) — not all of it.

Scope. This is the standard workflow: compute three dimensions by row reduction and read the fourth off the formula, then verify by exhibiting that many independent common vectors. It is far cheaper than solving the \( 5 \)-variable system \( \sum \lambda_i u_i = \sum \mu_j w_j \) for the intersection directly.

Example 2 (binary codes: how many codewords have even weight?). Work over \( \mathbb{F}_2 \) in \( V = \mathbb{F}_2^{7} \), so \( \dim V = 7 \) bits. Let \( C_1 \) be the Hamming \( [7,4] \) code, the kernel of the parity-check matrix \( H \in \mathbb{F}_2^{3 \times 7} \) whose seven columns are the seven nonzero vectors of \( \mathbb{F}_2^{3} \) (column \( i \) is the binary expansion of \( i \)), and let \( C_2 = \{ x \in V : x_1 + x_2 + \dots + x_7 = 0 \} \) be the even-weight code. How many codewords does \( C_1 \) have of even weight?

\( \dim C_1 = 4 \) and \( \dim C_2 = 6 \).

The columns of \( H \) include \( 100, 010, 001 \) (positions \( 4, 2, 1 \)), so its column rank, hence \( \operatorname{rank} H \), is \( 3 \); rank–nullity gives \( \dim \ker H = 7 - 3 = 4 \), i.e. \( 2^4 = 16 \) codewords. \( C_2 \) is the kernel of the nonzero linear functional \( x \mapsto \sum_i x_i \), hence a hyperplane: \( \dim C_2 = 7 - 1 = 6 \), i.e. \( 64 \) vectors. A

\( C_1 \not\subseteq C_2 \), and therefore \( C_1 + C_2 = V \), so \( \dim (C_1 + C_2) = 7 \).

Columns \( 1, 2, 3 \) of \( H \) are \( 001, 010, 011 \), which sum to \( 000 \), so the vector \( x \) with support \( \{1,2,3\} \) lies in \( C_1 \) and has weight \( 3 \) — odd, so \( x \notin C_2 \). Then \( C_1 + C_2 \) strictly contains the hyperplane \( C_2 \), and a subspace strictly containing a hyperplane of \( V \) is \( V \). B

Grassmann's formula gives the even-weight subcode: \[ \dim (C_1 \cap C_2) = \dim C_1 + \dim C_2 - \dim (C_1 + C_2) = 4 + 6 - 7 = 3, \] hence \( |C_1 \cap C_2| = 2^{3} = 8 \) codewords.

The formula, applied over \( \mathbb{F}_2 \) exactly as over \( \mathbb{R} \) — nothing in the proof used characteristic zero. Over a finite field a dimension converts to a count: a \( k \)-dimensional subspace of \( \mathbb{F}_q^N \) has \( q^k \) elements. B

Cross-check against the weight enumerator of the Hamming \( [7,4] \) code, whose \( 16 \) codewords are distributed by weight as \( A_0 = 1 \), \( A_3 = 7 \), \( A_4 = 7 \), \( A_7 = 1 \) (no codewords of weight \( 1, 2, 5 \) or \( 6 \)). The even-weight ones number \( A_0 + A_4 = 1 + 7 = 8 \).

The standard weight distribution of this code; \( 1 + 7 + 7 + 1 = 16 \) confirms all codewords are accounted for. The independent count agrees with Step 3, which used no information about weights beyond the existence of one odd-weight codeword. A

\[ \dim (C_1 \cap C_2) = 4 + 6 - 7 = 3, \qquad |C_1 \cap C_2| = 2^3 = 8 \ \text{codewords of } 7 \text{ bits} . \]

Reading. Exactly \( 8 \) of the \( 16 \) Hamming codewords have even weight: the zero word and the seven words of weight \( 4 \). Half the code lies in the even-weight hyperplane, which is what “\( C_1 \) is not contained in \( C_2 \)” forces — intersecting a subspace with a hyperplane it does not lie in always costs exactly one dimension.

Scope. The argument is generic: for any \( [N, k] \) code \( C \) over \( \mathbb{F}_q \) and any hyperplane \( P \), \( \dim (C \cap P) = k \) if \( C \subseteq P \) and \( k - 1 \) otherwise, giving \( q^{k-1} \) codewords in the second case.

Problems

Let \( U \) and \( W \) be two distinct planes through the origin in \( \mathbb{R}^3 \). Prove that \( U \cap W \) is a line, and verify the count for \( U = \{ (x,y,z) : z = 0 \} \) and \( W = \{ (x,y,z) : x = 0 \} \).
Solution

Both planes have dimension \( 2 \), and \( U + W \subseteq \mathbb{R}^3 \) so \( \dim (U + W) \le 3 \). Grassmann's formula gives \( \dim (U \cap W) = 2 + 2 - \dim (U + W) \ge 4 - 3 = 1 \). If \( \dim (U \cap W) = 2 \) then \( U \cap W \) is a two-dimensional subspace of the two-dimensional space \( U \), hence equals \( U \), and likewise equals \( W \), contradicting \( U \ne W \). So \( \dim (U \cap W) = 1 \) exactly: a line. (Consequently \( \dim (U + W) = 2 + 2 - 1 = 3 \), i.e. two distinct planes always span all of \( \mathbb{R}^3 \).)

For the explicit pair, \( U = \operatorname{span}\{ (1,0,0), (0,1,0) \} \) and \( W = \operatorname{span}\{ (0,1,0), (0,0,1) \} \). A vector lies in both exactly when its third and first coordinates vanish, so \( U \cap W = \operatorname{span}\{ (0,1,0) \} \), of dimension \( 1 \); and \( U + W = \mathbb{R}^3 \), of dimension \( 3 \). The identity reads \( 3 + 1 = 2 + 2 \).
In \( \mathbb{R}^5 \) let \( U = \operatorname{span}\{ (1,1,0,1,0), (0,1,1,0,1) \} \) and \( W = \operatorname{span}\{ (1,2,1,1,1), (1,0,-1,1,-1), (0,1,1,1,0) \} \). Compute all four dimensions in Grassmann's formula and describe the relationship between \( U \) and \( W \).
Solution

Write \( a_1 = (1,1,0,1,0) \) and \( a_2 = (0,1,1,0,1) \); they are independent (coordinates \( 1 \) and \( 3 \)), so \( \dim U = 2 \). For \( W \), name the spanning vectors \( b_1, b_2, b_3 \) and notice \( b_1 = a_1 + a_2 \) and \( b_2 = a_1 - a_2 \). Hence \( \operatorname{span}\{ b_1, b_2 \} = \operatorname{span}\{ a_1, a_2 \} = U \), because \( a_1 = \tfrac{1}{2}(b_1 + b_2) \) and \( a_2 = \tfrac{1}{2}(b_1 - b_2) \).

Is \( b_3 = (0,1,1,1,0) \) in \( U \)? Solving \( \lambda a_1 + \mu a_2 = b_3 \): the first coordinate forces \( \lambda = 0 \), the third forces \( \mu = 1 \), but then the fourth coordinate would be \( 0 \ne 1 \). So \( b_3 \notin U \) and \( \dim W = 3 \).

Therefore \( U \subseteq W \), giving \( U \cap W = U \) (dimension \( 2 \)) and \( U + W = W \) (dimension \( 3 \)). The formula reads \( 3 + 2 = 2 + 3 \). The moral: the spanning set of \( W \) disguised the fact that \( W \) already contains \( U \); the four dimensions detect the containment, since \( \dim (U + W) = \dim W \) happens exactly when \( U \subseteq W \).
Let \( \dim V = N \) and let \( U, W \subseteq V \) have dimensions \( m \) and \( n \). Prove \( \dim (U \cap W) \ge m + n - N \), show the bound is attained for every admissible triple, and apply it: must two \( 6 \)-dimensional subspaces of \( \mathbb{R}^{10} \) intersect in dimension at least \( 2 \)? Must two \( 4 \)-dimensional subspaces of \( \mathbb{R}^{10} \) intersect at all beyond \( \{0\} \)?
Solution

Bound. \( U + W \) is a subspace of \( V \), so \( \dim (U + W) \le N \). Grassmann gives \( \dim (U \cap W) = m + n - \dim (U + W) \ge m + n - N \). Since dimensions are non-negative, the sharp statement is \( \dim (U \cap W) \ge \max(0, \, m + n - N) \).

Attainment. Let \( p = \max(0, m + n - N) \) and take \( U = \operatorname{span}(e_1, \dots, e_m) \), \( W = \operatorname{span}(e_{m-p+1}, \dots, e_{m-p+n}) \). The largest index used is \( m - p + n \le N \) by the definition of \( p \), so \( W \subseteq V \) is legitimate; the two index sets overlap in exactly \( \{ m-p+1, \dots, m \} \), which has \( p \) elements, so \( U \cap W = \operatorname{span}(e_{m-p+1}, \dots, e_m) \) has dimension \( p \).

Applications. With \( m = n = 6 \), \( N = 10 \): \( \dim (U \cap W) \ge 6 + 6 - 10 = 2 \) — yes, they must share at least a plane, and \( U = \operatorname{span}(e_1, \dots, e_6) \), \( W = \operatorname{span}(e_5, \dots, e_{10}) \) shows \( 2 \) is achieved. With \( m = n = 4 \), \( N = 10 \): the bound is \( 4 + 4 - 10 = -2 \le 0 \), so nothing is forced, and indeed \( U = \operatorname{span}(e_1, \dots, e_4) \), \( W = \operatorname{span}(e_5, \dots, e_8) \) meet only in \( \{0\} \).
Over \( \mathbb{F}_2 \), let \( V = \mathbb{F}_2^{8} \), let \( C = \{ x \in V : x_1 + x_2 + x_3 + x_4 = 0 \ \text{and} \ x_5 + x_6 + x_7 + x_8 = 0 \} \), and let \( P = \{ x \in V : x_1 + x_5 = 0 \} \). Compute \( \dim C \), \( \dim P \), \( \dim (C \cap P) \) and \( \dim (C + P) \), and say how many vectors each of the four subspaces contains. Then exhibit three subspaces of \( \mathbb{F}_2^{2} \) for which the naive three-set inclusion–exclusion formula fails.
Solution

Dimensions. \( C \) is the kernel of the map \( x \mapsto (x_1 + x_2 + x_3 + x_4, \ x_5 + x_6 + x_7 + x_8) \in \mathbb{F}_2^2 \), which is surjective (take \( x = e_1 \) and \( x = e_5 \)), so by rank–nullity \( \dim C = 8 - 2 = 6 \). \( P \) is the kernel of the nonzero functional \( x \mapsto x_1 + x_5 \), so \( \dim P = 7 \).

Is \( C \subseteq P \)? No: \( x = e_1 + e_2 \) satisfies both defining equations of \( C \) (the first sum is \( 1 + 1 = 0 \), the second is \( 0 \)), but \( x_1 + x_5 = 1 + 0 = 1 \ne 0 \). Hence \( C + P \) strictly contains the hyperplane \( P \), so \( C + P = V \) and \( \dim (C + P) = 8 \). Grassmann then gives \( \dim (C \cap P) = 6 + 7 - 8 = 5 \).

Counts. \( |C| = 2^6 = 64 \), \( |P| = 2^7 = 128 \), \( |C \cap P| = 2^5 = 32 \), \( |C + P| = 2^8 = 256 \). Note the identity is about dimensions, not cardinalities: \( 256 \cdot 32 = 64 \cdot 128 = 8192 \), so over a finite field the formula exponentiates into a multiplicative statement \( |U + W| \cdot |U \cap W| = |U| \cdot |W| \).

Three subspaces. In \( \mathbb{F}_2^2 \) take \( L_1 = \{00, 10\} \), \( L_2 = \{00, 01\} \), \( L_3 = \{00, 11\} \), each of dimension \( 1 \). All pairwise intersections and the triple intersection are \( \{00\} \), of dimension \( 0 \), while \( L_1 + L_2 + L_3 = \mathbb{F}_2^2 \) has dimension \( 2 \). The naive formula would predict \( 1 + 1 + 1 - 0 - 0 - 0 + 0 = 3 \gt 2 \). The correct iterated count is \( \dim(L_1 + L_2 + L_3) = \dim(L_1 + L_2) + \dim L_3 - \dim((L_1 + L_2) \cap L_3) = 2 + 1 - 1 = 2 \), and the point of failure is visible: \( (L_1 + L_2) \cap L_3 = L_3 \) is not captured by any pairwise intersection.
Give a second proof of Grassmann's formula using the rank–nullity theorem: consider the map \( \sigma : U \oplus W \to V \), \( \sigma(u, w) = u - w \), on the external direct sum. Then verify every number in the proof against Example 1 above.
Solution

The space \( U \oplus W \). On the set \( U \times W \) define \( (u_1, w_1) + \lambda (u_2, w_2) = (u_1 + \lambda u_2, \ w_1 + \lambda w_2) \); this is a vector space over \( F \), and if \( \{ x_i \}_{i \le m} \) is a basis of \( U \) and \( \{ y_j \}_{j \le n} \) a basis of \( W \), then \( \{ (x_i, 0) \} \cup \{ (0, y_j) \} \) is a basis of it (it spans since \( (u, w) = (u,0) + (0,w) \), and a vanishing combination has vanishing \( U \)-part and \( W \)-part separately). Hence \( \dim (U \oplus W) = m + n = \dim U + \dim W \).

Linearity, image, kernel. \( \sigma \) is linear: \( \sigma((u_1,w_1) + \lambda(u_2,w_2)) = (u_1 + \lambda u_2) - (w_1 + \lambda w_2) = \sigma(u_1,w_1) + \lambda \sigma(u_2,w_2) \). Its image is \( \{ u - w \} = U + W \), since \( W = -W \) is a subspace. Its kernel is \( \{ (u,w) : u = w \} = \{ (x,x) : x \in U \cap W \} \), and \( x \mapsto (x,x) \) is a linear bijection from \( U \cap W \) onto that kernel, so \( \dim \ker \sigma = \dim (U \cap W) \).

Conclusion. Rank–nullity applied to \( \sigma \) on the finite-dimensional domain \( U \oplus W \) gives \( \dim \operatorname{im} \sigma + \dim \ker \sigma = \dim (U \oplus W) \), that is \( \dim (U + W) + \dim (U \cap W) = \dim U + \dim W \). \( \blacksquare \)

Numerical check against Example 1. There \( \dim U = \dim W = 3 \), so the domain \( U \oplus W \) has dimension \( 6 \) — concretely, pairs \( (u, w) \) with six free coefficients. The image is \( U + W \), of dimension \( 4 \), and the kernel is the diagonal copy of \( U \cap W = \operatorname{span}\{ (1,0,1,0,1), (0,1,0,1,0) \} \), of dimension \( 2 \). Rank–nullity reads \( 4 + 2 = 6 \), matching \( 3 + 3 \). Note also that \( \sigma \) is not injective even though \( U \ne W \): its kernel has dimension \( 2 \), one dimension for each independent vector the two subspaces share.