The Dimension Function — Linear Algebra

The subset lattice and subspace lattice. We first demonstrate that the power set $\mathcal{P}(V)$ of a vector space $$V$$ and the collection $\operatorname{Sub}(V)$ of all subspaces of $$V$$ are lattices. In particular, $\mathcal{P}(V)$ is a distributive lattice and $\operatorname{Sub}(V)$ is a modular one. This order-theoretic perspective will help us appreciate the concept of dimension.

Proposition 3.2.1. Let $$V$$ be a vector space. Then, the partially ordered set $\mathcal P(V)$ is a lattice, with join and meet given by

\[S\vee T=S\cup T \quad \text{and} \quad S\wedge T=S\cap T\]

for all $$S,T\in\mathcal P(V)$.$ Its least and greatest elements are $\varnothing$ and $$V$,$ respectively.

Proof. Since $$S,T\subseteq V$,$ we have $S\cup T\subseteq V$ and $$S\cap T\subseteq V$.$ Let $$A\in\mathcal P(V)$.$ If $A\supseteq S$ and $$A\supseteq T$,$ then $$A\supseteq S\cup T$.$ Hence $S\cup T$ is the supremum for $$S$$ and $$T$.$ On the other hand, if $A\subseteq S$ and $$A\subseteq T$,$ then $$A\subseteq S\cap T$.$ Hence $S\cap T$ is the infimum for $$S$$ and $$T$.$ By Proposition 1.3.7, $(\mathcal P(V),\cup)$ and $(\mathcal P(V),\cap)$ are an upper semilattice and lower semilattice, respectively. Furthermore, since $S\cap T \subseteq S$ and $$S\subseteq S\cup T$,$ we have $S\cap (S\cup T) = S$ and $S\cup (S\cap T) = S$ for all $$S,T\in \mathcal P(V)$.$ By Definition 1.3.9, $(\mathcal P(V),\cup,\cap)$ is a lattice. $\square$

Proposition 3.2.2. Let $$V$$ be a vector space. Then, the partially ordered set $\operatorname{Sub}(V)$ is a lattice, with join and meet given by

\[U\vee W=U+W \quad \text{and} \quad U\wedge W=U\cap W\]

for all $$U,W\in\operatorname{Sub}(V)$.$ The least and greatest elements of $\operatorname{Sub}(V)$ are $\{0_V\}$ and $$V$,$ respectively.

Proof. Since $$U+W$$ is a subspace of $$V$$ and is the supremum for $$U$$ and $$W$$ by Theorem 2.2.12, $(\operatorname{Sub}(V), +)$ is an upper semilattice. On the other hand, by Theorem 2.2.9, $U\cap W$ is a subspace of $$W$$ and is the infimum for $$U$$ and $$W$.$ Hence $(\operatorname{Sub}(V),\cap)$ is a lower semilattice. Furthermore, since $U\subseteq U+W$ and $$U\cap W\subseteq U$,$ we have $U\cap (U+W) = U$ and $U + (U \cap W) = U$ for all $$U,W\in \operatorname{Sub}(V)$.$ By Definition 1.3.9, $(\operatorname{Sub}(V), +, \cap)$ is a lattice. $\square$

We now compare the two structures. Although both lattices are ordered by inclusion, their different join operations lead to different structural properties. The subset lattice is distributive, whereas the subspace lattice is modular but need not be distributive.

Theorem 3.2.3. Let $$V$$ be a vector space.

The subset lattice $\mathcal{P}(V)$ is distributive.
The subspace lattice $\operatorname{Sub}(V)$ is modular.

Proof. (1) By the definitions of union and intersection, union is distributive over intersection and vice versa. Hence $\mathcal{P}(V)$ is distributive. (2) Let $W_1, W_2, W_3 \in \operatorname{Sub}(V)$ and $$W_1\subseteq W_3$.$ Suppose $$w\in W_1 + (W_2 \cap W_3)$.$ Then there exist $w_1\in W_1$ and $w_2\in W_2 \cap W_3$ such that $$w = w_1 + w_2$.$ Hence $$w=w_1+w_2 \in W_1 + W_2$.$ Furthermore, since $$W_1 \subseteq W_3$,$ we have $w_1 \in W_3$ and $$w_2\in W_3$.$ Since $$W_3\in \operatorname{Sub}(V)$,$ $$w=w_1 + w_2 \in W_3$.$ Thus $$W_1 + (W_2 \cap W_3) \subseteq (W_1 + W_2) \cap W_3$.$ We now suppose $$w \in (W_1 + W_2) \cap W_3$.$ Then there exist $w_1 \in W_1$ and $w_2 \in W_2$ such that $$w = w_1 + w_2$.$ Since $W_1 \subseteq W_3$ and $$W_3 \in \operatorname{Sub}(V)$,$ $w_1 \in W_3$ so that $$w_2 = w - w_1 \in W_3$.$ Thus $$w = w_1 + w_2 \in W_1 + (W_2 \cap W_3)$,$ so $$W_1 + (W_2 \cap W_3) \supseteq (W_1 + W_2) \cap W_3$.$ It is concluded that $$W_1 + (W_2 \cap W_3) = (W_1 + W_2) \cap W_3$,$ and, by Definition 1.3.13, $\operatorname{Sub}(V)$ is modular. $\square$

Galois connections between the two lattices. The subset lattice $\mathcal P(V)$ and the subspace lattice $\operatorname{Sub}(V)$ exhibit fundamentally different order-theoretic structures. Nevertheless, there is a natural relationship between them—Galois connections.¹ We first introduce this concept for arbitrary posets and then apply it to the span and inclusion maps. Along the way, the span operator is reinterpreted as a map naturally arising from the relationship between the two lattices.

Definition 3.2.4. Let $(P,\le_P)$ and $(Q,\le_Q)$ be posets, and let $F \colon P\to Q$ and $G \colon Q\to P$ be maps. The pair $$(F,G)$$ is called a Galois connection between these posets if, for every $p\in P$ and $$q\in Q$,$

\[F(p)\le_Q q\iff p\le_P G(q).\]

In this case, $$F$$ is called the left adjoint of $$G$,$ and $$G$$ is called the right adjoint of $$F$.$ We write $$F\dashv G$.$

Theorem 3.2.5. Suppose that two lattices $$L$$ and $$M$$ have a Galois connection, and $$F$$ and $$G$$ are the left adjoint and the right adjoint, respectively. Then the following hold:

$$F$$ and $$G$$ are monotone;
$$F$$ and $$G$$ preserve join and meet, respectively;
$G \circ F$ is a closure operator.

Proof. (1) Suppose $l, l' \in L$ and $$l \le l'$.$ Since $$F(l') \le F(l')$,$ $$l' \le G(F(l'))$.$ It follows that $$l \le l' \le G(F(l'))$,$ which is equivalent to $$F(l) \le F(l')$.$ Hence the left adjoint $$F$$ is monotone. It follows from duality that the right adjoint is also monotone. (2) Let $$l, l' \in L$.$ Since $$F$$ is monotone, by Theorem 1.3.11, $$F(l \vee l') \ge F(l) \vee F(l')$.$ We now show the reverse inequality. Firstly, we have $F(l) \le F(l) \vee F(l')$ and $$F(l') \le F(l) \vee F(l')$.$ Since $$G$$ is monotone, $G(F(l)) \le G(F(l) \vee F(l'))$ and $$G(F(l')) \le G(F(l) \vee F(l'))$.$ Since $x \le G(F(x))$ for all $$x\in L$,$ it follows that $l \le G(F(l)) \le G(F(l) \vee F(l'))$ and $$l' \le G(F(l')) \le G(F(l) \vee F(l'))$.$ Therefore $$l \vee l' \le G(F(l) \vee F(l'))$,$ which is equivalent to $$F(l \vee l') \le F(l) \vee F(l')$.$ Consequently, $$F(l \vee l') = F(l) \vee F(l')$,$ so $$F$$ preserves join. It follows from duality that $$G$$ preserves meet. (3) Put $$\operatorname{cl} = G \circ F$.$ Since $$F(l) \le F(l)$,$ $$l \le G(F(l)) = \operatorname{cl}(l)$.$ On the other hand, we have $F(\operatorname{cl}(l)) \le F(l)$ from $$G(F(l)) \le G(F(l))$.$ Hence, if $l \le G(m)$ then $$F(\operatorname{cl}(l)) \le F(l) \le m$.$ By Theorem 2.4.4, $\operatorname{cl}$ is a closure operator. $\square$

We now apply these general results to the subset and subspace lattices of a vector space.

Definition 3.2.6. Let $$V$$ be a vector space. The span map is the function

\[\sigma \colon \mathcal{P}(V) \to \operatorname{Sub}(V), \qquad S \mapsto \operatorname{span}(S).\]

Theorem 3.2.7. Let $\sigma$ be the span map, and let $\iota \colon \operatorname{Sub}(V) \hookrightarrow \mathcal{P}(V)$ be the inclusion map. Then the pair $(\sigma, \iota)$ is a Galois connection between $\mathcal{P}(V)$ and $$\operatorname{Sub}(V)$.$ Hence the composite

\[\iota \circ \sigma \colon \mathcal{P}(V) \longrightarrow \mathcal{P}(V)\]

is a closure operator on $$\mathcal{P}(V)$.$

Proof. Let $S \in \mathcal{P}(V)$ and $$W \in \operatorname{Sub}(V)$.$ Suppose $\sigma(S) \subseteq W$ and let $$s\in S$.$ Since $$s \in \operatorname{span}(S)$,$ $$s \in \sigma(S) \subseteq W$.$ Hence $$S \subseteq \iota(W)$.$ Conversely, suppose $S \subseteq \iota(W)$ and let $$v \in \sigma(S)$.$ Then there exist a finite set $$I$$ and indexed families $\{s_i\}_{i\in I}$ in $$S$$ and $\{a_i\}_{i\in I}$ in $$F$$ such that $$v=\sum_{i\in I}a_is_i$.$ Since $\{s_i : i\in I\} \subseteq S \subseteq \iota(W) = W$ and $$W$$ is a subspace, $$v=\sum_{i\in I}a_is_i \in W$.$ Hence $$\sigma(S) \subseteq W$.$ By Definition 3.2.4, $(\sigma, \iota)$ is a Galois connection. Furthermore, by Theorem 3.2.5, $\iota \circ \sigma$ is a closure operator on $$\mathcal{P}(V)$.$ $\square$

The adjunction $\sigma \dashv \iota$ gives a structural interpretation of the span operator. Since $$\sigma \circ \iota = \operatorname{id}_{\operatorname{Sub}(V)}$,$ the composite $\iota \circ \sigma$ is precisely the span operator on $$\mathcal{P}(V)$,$ whose fixed points are the subspaces of $$V$.$

Remark 3.2.8. In category theory, the order-theoretic concept of Galois connections leads to a generalized concept at higher levels of abstraction. Every poset $$P$$ can be regarded as a category whose objects are the elements of $$P$,$ with a unique morphism $p \to q$ whenever $$p \leq q$,$ and no morphism otherwise. From this perspective, monotone maps become functors, and a Galois connection is precisely an adjunction between the corresponding categories. Consequently, $\mathcal{P}(V)$ and $$\operatorname{Sub}(V)$,$ regarded as categories, are related by the adjoint functors $$\sigma \dashv \iota$.$ This categorical viewpoint emphasizes the relationship between the two structures through the functors connecting them, rather than considering their internal order-theoretic properties in isolation.

Dimension as a rank function. Now we are ready to consider dimension as a function. For a finite-dimensional vector space, the dimension function is a rank function on the subspace lattice. This allows us to establish fundamental properties of dimension easily, including the Grassmann’s dimension formula.² Furthermore, by composing the dimension function with the span map, we obtain a function that assigns a rank to every subset of $$V$.$ This induced rank function is generally only submodular, reflecting the fact that the span map preserves joins but need not preserve meets. Throughout the remainder of this section, we assume that $$V$$ is finite-dimensional, with $$\dim V = n$.$

Theorem 3.2.9. The dimension function

\[\rho \colon \operatorname{Sub}(V) \to \{0,1,\ldots,n\}, \qquad \rho(W) = \dim W\]

is the rank function on the subspace lattice $$\operatorname{Sub}(V)$.$

Proof. The empty set $\varnothing$ is a basis for the zero subspace $$\{0_V\}$,$ so $$\rho(\{0_V\}) = \dim \{0_V\} = 0$.$ Now suppose $U,W\in \operatorname{Sub}(V)$ and $$U\lessdot W$.$ Let $$B$$ be a basis for $$U$.$ Since $$B$$ is a linearly independent subset of $$W$,$ there exists a basis $$C$$ for $$W$$ such that $B \subseteq C$ by Theorem 3.1.13. Moreover, we have $$B \subset C$,$ since otherwise $$B = C$$ so that $$U = W$.$ Suppose, for the sake of contradiction, that $$|C| > |B| + 1$.$ Then, there exist $$c \in C\setminus B$,$ so that $W' = \operatorname{span}(B \cup \{c\})$ becomes a subspace satisfying $$U\subset W' \subset W$.$ This contradicts to our assumption that $$W$$ is the immediate successor of $$U$.$ It therefore follows that $$|C| = |B| + 1$,$ proving $$\rho(W) = \rho(U) + 1$.$ By Definition 1.3.16, $\rho$ is the rank function on $$\operatorname{Sub}(V)$.$ $\square$

Corollary 3.2.10 (Grassmann’s formula). Let $$V$$ be a vector space. Then, for all $$U, W \in \operatorname{Sub}(V)$,$

\[\dim(U + W) + \dim(U \cap W) = \dim U + \dim W.\]

Proof. Since $\operatorname{Sub}(V)$ is a modular lattice and $\rho$ is the rank function, by Theorem 1.3.20, $\rho$ is modular. Hence we have $\rho(U\vee W) - \rho(U) = \rho(W) - \rho(U\wedge W)$ for all $$U, W \in \operatorname{Sub}(V)$.$ By Proposition 3.2.2 and the definition of $$\rho$,$ this is equivalent to $$\dim(U + W) - \dim U = \dim W - \dim(U \cap W)$.$ Rearranging gives the desired identity. $\square$

Definition 3.2.11. The linear rank function on the power set of a vector space $$V$$ is the function

\[r \colon \mathcal{P}(V) \to \{0,1,\ldots,n\}, \qquad r(S) = \rho(\sigma(S)).\]

Proposition 3.2.12. The linear rank function $$r$$ satisfies the following properties:

$$r(\varnothing) = 0$;$
$$r$$ is monotone;
$$r$$ is submodular.

Proof. (1) Since $\sigma(\varnothing) = \{0_V\}$ and $$\rho(\{0_V\}) = 0$,$ $$r(\varnothing) = 0$.$ (2) By Theorem 3.2.5, $\sigma$ is monotone. Since $\rho$ is also monotone, the composite $$r$$ is monotone. (3) Since $\sigma$ preserves joins and $\rho$ is monotone,

\[\begin{align} r(S \vee T) - r(S) &= \rho(\sigma(S \vee T)) - \rho(\sigma(S))\\ &= \rho(\sigma(S) \vee \sigma(T)) - \rho(\sigma(S))\\ &= \rho(\sigma(T)) - \rho(\sigma(S) \wedge \sigma(T)). \end{align}\]

Moreover, since $\sigma$ is monotone, we have $\sigma(S \wedge T) \le \sigma(S) \wedge \sigma(T)$ by Theorem 1.3.11. It therefore follows from monotonicity of $\rho$ that

\[\begin{align} r(S \vee T) - r(S) &= \rho(\sigma(T)) - \rho(\sigma(S) \wedge \sigma(T))\\ &\le \rho(\sigma(T)) - \rho(\sigma(S \wedge T))\\ &= r(T) - r(S \wedge T). \end{align}\]

Hence $$r$$ is submodular. $\square$

Remark 3.2.13. The difference between the two sides of the submodular inequality can be expressed more precisely as

\[r(S) + r(T) - r(S \vee T) - r(S \wedge T) = \rho(\sigma(S) \wedge \sigma(T)) - \rho(\sigma(S \wedge T)).\]

Since $$\sigma(S \vee T) \le \sigma(S) \vee \sigma(T)$,$ the submodular inequality becomes equality if and only if

\[\operatorname{span}(S \cap T) = \operatorname{span}(S) \cap \operatorname{span}(T).\]

In the term Galois connection, “Galois” refers to the French mathematician Évariste Galois (1811–1832). Despite dying before the age of 21, he made foundational contributions to modern algebra. His central insight was to associate algebraic equations with groups of permutations of their roots and to use the structure of those groups to determine whether the equations can be solved by radicals. This viewpoint eventually developed into what is now called Galois theory and also played a major role in the emergence of abstract group theory. His life was unusually short and turbulent: Galois was politically active, was imprisoned more than once, and died on May 31, 1832, after being wounded in a duel the previous day. Much of the mathematical importance of his work was recognized only later; Joseph Liouville eventually published Galois’s papers in 1846. In English-language mathematics, his surname is commonly pronounced /ɡælˈwɑ/. ↩
In the term Grassmann’s dimension formula, “Grassmann” refers to the German mathematician Hermann Günther Grassmann (1809–1877), known in his days as a linguist. He was one of the early pioneers of abstract linear algebra and developed a highly original theory of vector-like quantities. Grassmann introduced ideas closely related to linear independence, dimension, span, and what later became exterior algebra. His work was far ahead of its time and was not widely appreciated at first, but it later became fundamental in linear algebra, geometry, and differential geometry. In English-language mathematics, his surname is pronounced /ˈɡrɑːsmən/. ↩