Finite-dimensional vector spaces

Let \(X = (x_1, \ldots, x_n)\) generate \(E\) and let \(Y\) be a free family of \(E\). Suppose, for contradiction, that \(Y\) has at least \(n + 1\) elements. We prove by induction on \(k \in \llbracket 0, n \rrbracket\) the property $$ \mathcal{P}(k) : \ E \text{ is generated by a family of } n \text{ vectors: the first } n - k \text{ from } X, \text{ the last } k \text{ from } Y. $$

• Initialization. For \(k = 0\): \(E\) is generated by \((x_1, \ldots, x_n)\), the original \(X\). This is the hypothesis.
• Heredity. Suppose \(\mathcal{P}(k)\) holds for some \(k \in \llbracket 0, n - 1 \rrbracket\). So \(E\) is generated by \((x_1, \ldots, x_{n-k}, y_1, \ldots, y_k)\) for some labelling. As \(Y\) has at least \(n + 1\) elements, pick \(y_{k+1} \in Y\) distinct from \(y_1, \ldots, y_k\). By the induction hypothesis \(y_{k+1}\) is a linear combination of \((x_1, \ldots, x_{n-k}, y_1, \ldots, y_k)\): $$ y_{k+1} = \lambda_1 x_1 + \cdots + \lambda_{n-k} x_{n-k} + \mu_1 y_1 + \cdots + \mu_k y_k. $$ The coefficients \(\lambda_1, \ldots, \lambda_{n-k}\) are not all zero, otherwise \(y_{k+1}\) would be a linear combination of \(y_1, \ldots, y_k\) and the subfamily \((y_1, \ldots, y_{k+1})\) of \(Y\) would be dependent, contradicting freeness of \(Y\). Pick an index \(i\) with \(\lambda_i \ne 0\); up to relabelling, \(\lambda_{n-k} \ne 0\). Solve for \(x_{n-k}\) as a linear combination of \((x_1, \ldots, x_{n-k-1}, y_1, \ldots, y_{k+1})\). Hence \(E\) is generated by \((x_1, \ldots, x_{n-k-1}, y_1, \ldots, y_{k+1})\): \(\mathcal{P}(k + 1)\) holds.

At \(k = n\): \(E\) is generated by \((y_1, \ldots, y_n)\). Then \(y_{n+1} \in E\) is a linear combination of \((y_1, \ldots, y_n)\), so the subfamily \((y_1, \ldots, y_{n+1})\) of \(Y\) is dependent --- contradicting freeness of \(Y\). Hence \(Y\) cannot have more than \(n\) elements.

Initialize the family \(\mathcal{B} := (x_1, \ldots, x_p)\) --- free by hypothesis. Loop over \(k\) from \(p + 1\) to \(n\):

• if the family \(\mathcal{B}\) extended by \(x_k\) is still free, replace \(\mathcal{B}\) by this extended family --- the new \(\mathcal{B}\) is again free;
• if not, leave \(\mathcal{B}\) unchanged and continue the loop.

At each step \(\mathcal{B}\) is free, so the final \(\mathcal{B}\) is free. It remains to show that the final \(\mathcal{B}\) generates \(E\). Since \((x_1, \ldots, x_n)\) generates \(E\), it suffices to show that every \(x_k\) is a linear combination of vectors of \(\mathcal{B}\):

• if \(x_k\) was added to \(\mathcal{B}\) during the loop, it is in \(\mathcal{B}\), so a (trivial) linear combination;
• if \(x_k\) was not added, this is because \(\mathcal{B}\) extended by \(x_k\) was dependent at that step; by the freeness-extension proposition (chapter Vector spaces, Proposition « Properties of free and dependent families »), \(x_k\) is a linear combination of \(\mathcal{B}\) at that step, hence of the final \(\mathcal{B}\).

Hence the final \(\mathcal{B}\) is free and generating: a basis of \(E\) containing \(x_1, \ldots, x_p\) and a subfamily of \(x_{p+1}, \ldots, x_n\).

• Base extraite. Apply the algorithm with \(p = 0\): \(\mathcal{B}\) starts as the empty family (free), the loop processes all \(n\) generators; the final \(\mathcal{B}\) is a basis contained in the original generating family.
• Base incomplète. Let \(\mathcal{L} = (\ell_1, \ldots, \ell_p)\) be free in \(E\). Pick a finite generating family \((g_1, \ldots, g_q)\) of \(E\). The concatenated family \((\ell_1, \ldots, \ell_p, g_1, \ldots, g_q)\) generates \(E\) (it contains a generating family) and its first \(p\) vectors are free. Apply the algorithm: the resulting basis contains \(\ell_1, \ldots, \ell_p\) and a subfamily of \(g_1, \ldots, g_q\).
• Existence of a finite basis. A consequence of either: extract a basis from any generating family of \(E\).

\(E\) has a finite basis by the existence-of-a-finite-basis theorem. Let \(\mathcal{B}\) and \(\mathcal{B}'\) be two bases of \(E\), of respective cardinals \(n\) and \(n'\). As \(\mathcal{B}\) generates \(E\) and \(\mathcal{B}'\) is free, the maximal-free theorem gives \(n' \le n\). By symmetry, \(n \le n'\). Hence \(n = n'\): all bases have the same cardinal.

• Free \(\le n\). \(E\) has a basis \(\mathcal{B}\) of cardinal \(n\) which generates \(E\). By the maximal-free theorem, every free family has at most \(n\) elements.
• Generating \(\ge n\). Let \(\mathcal{G}\) be a finite generating family of \(E\). By the « base extraite » theorem, \(\mathcal{G}\) contains a basis of \(E\), which has cardinal \(n\). Hence \(\#\mathcal{G} \ge n\). (If \(\mathcal{G}\) is infinite, it has \(\ge n\) elements a fortiori.)

\((1) \Rightarrow (2)\) and \((1) \Rightarrow (3)\) are by definition of « basis ». We prove \((2) \Rightarrow (1)\) and \((3) \Rightarrow (1)\).

• \((2) \Rightarrow (1)\). Suppose \(\mathcal{F}\) is free of cardinal \(n\). By the « base incomplète » theorem, \(\mathcal{F}\) can be completed into a basis of \(E\). By the cardinal bound, this basis has cardinal \(n\). So no vectors were added: \(\mathcal{F}\) is already a basis.
• \((3) \Rightarrow (1)\). Suppose \(\mathcal{F}\) is generating of cardinal \(n\). By the « base extraite » theorem, one can extract a basis from \(\mathcal{F}\). By the cardinal bound, this basis has cardinal \(n\). So no vectors were dropped: \(\mathcal{F}\) is already a basis.

Let \((e_1, \ldots, e_m)\) be a basis of \(E\) and \((f_1, \ldots, f_n)\) a basis of \(F\). We show that the concatenated family $$ \mathcal{B} := \bigl((e_1, 0_F), \ldots, (e_m, 0_F), (0_E, f_1), \ldots, (0_E, f_n)\bigr) $$ is a basis of \(E \times F\).

• Generating. Every \((x, y) \in E \times F\) writes \(x = \sum_{i=1}^m x_i e_i\) and \(y = \sum_{j=1}^n y_j f_j\), so $$ (x, y) = \sum_{i=1}^m x_i (e_i, 0_F) + \sum_{j=1}^n y_j (0_E, f_j) \in \mathrm{Vect}(\mathcal{B}). $$
• Free. Suppose \(\sum_{i=1}^m \lambda_i (e_i, 0_F) + \sum_{j=1}^n \mu_j (0_E, f_j) = (0_E, 0_F)\). Reading the two coordinates separately: \(\sum \lambda_i e_i = 0_E\) and \(\sum \mu_j f_j = 0_F\). By freeness of each basis, all \(\lambda_i = 0\) and all \(\mu_j = 0\).

So \(\mathcal{B}\) is a basis of \(E \times F\), of cardinal \(m + n = \dim E + \dim F\).

The family \((x_1, \ldots, x_n)\) generates \(\mathrm{Vect}(x_1, \ldots, x_n)\). By the cardinal bound applied to this subspace, \(\dim \mathrm{Vect}(x_1, \ldots, x_n) \le n\). Equality case: if the family is free, then it is a basis of \(\mathrm{Vect}(x_1, \ldots, x_n)\) (free + generating in its own span), so \(\dim = n\). Conversely if \(\dim \mathrm{Vect}(x_1, \ldots, x_n) = n\), then by the basis characterisation in dimension \(n\) applied in \(\mathrm{Vect}(x_1, \ldots, x_n)\) (dim \(n\) with a generating family of cardinal \(n\)), the family is a basis, hence free.

Both operations leave \(\mathrm{Vect}\) of the family unchanged, hence the dimension --- which is the rank --- unchanged.

Set \(n := \dim E\). Consider the set $$ \mathcal{N} := \{k \in \mathbb{N} : F \text{ contains a free family of cardinal } k\}. $$ \(\mathcal{N}\) is non-empty (it contains \(0\), the empty family) and bounded above by \(n\) (any free family of \(F\) is free in \(E\), hence has cardinal \(\le n\) by the cardinal bound). Let \(r := \max \mathcal{N} \le n\). Pick a free family \(\mathcal{L} = (\ell_1, \ldots, \ell_r)\) of \(F\) realising this maximum. We claim \(\mathcal{L}\) is a basis of \(F\). Freeness is by construction. For generating: take \(x \in F\). The extended family \((\ell_1, \ldots, \ell_r, x)\) has cardinal \(r + 1 > r\), so it is not in \(\mathcal{N}\) --- it is dependent. By the freeness-extension proposition (chapter Vector spaces), \(x\) is a linear combination of \(\mathcal{L}\). Hence \(\mathcal{L}\) generates \(F\). So \(F\) has a finite basis of cardinal \(r\), hence \(F\) is of finite dimension with \(\dim F = r \le n = \dim E\). Equality case. If \(\dim F = n\): \(\mathcal{L}\) is a free family of \(E\) of cardinal \(n = \dim E\), hence a basis of \(E\) by the basis characterisation in dimension \(n\). So \(\mathrm{Vect}(\mathcal{L}) = E\). But \(\mathrm{Vect}(\mathcal{L}) = F\) (basis of \(F\)). Hence \(F = E\). Conversely, \(F = E\) trivially gives \(\dim F = \dim E\).

Set \(r := \dim(F \cap G)\). The subspace \(F \cap G\) is finite-dimensional (subspace of \(F\) which is finite-dimensional, by the subspace-dimension theorem). Take a basis \((e_1, \ldots, e_r)\) of \(F \cap G\). Step 1 --- complete the basis of \(F \cap G\) to bases of \(F\) and \(G\). The family \((e_1, \ldots, e_r)\) is free in \(F\). By the « base incomplète » theorem applied in \(F\), complete to a basis \((e_1, \ldots, e_r, f_1, \ldots, f_p)\) of \(F\), where \(p = \dim F - r\). Similarly, complete to a basis \((e_1, \ldots, e_r, g_1, \ldots, g_q)\) of \(G\), where \(q = \dim G - r\). Step 2 --- \(F + G\) is generated by the concatenated family. Set \(\mathcal{C} := (e_1, \ldots, e_r, f_1, \ldots, f_p, g_1, \ldots, g_q)\). Every \(f + g \in F + G\) writes as a combination of vectors of bases of \(F\) and \(G\) (and combinations of \(\mathcal{C}\)). So \(F + G \subset \mathrm{Vect}(\mathcal{C})\). Conversely \(\mathcal{C} \subset F \cup G \subset F + G\), so \(\mathrm{Vect}(\mathcal{C}) \subset F + G\). Hence \(F + G = \mathrm{Vect}(\mathcal{C})\). Step 3 --- the family \(\mathcal{C}\) is free. Suppose $$ \sum_{i=1}^r \lambda_i e_i + \sum_{j=1}^p \mu_j f_j + \sum_{k=1}^q \nu_k g_k = 0_E. $$ Set \(v := \sum_{i=1}^r \lambda_i e_i + \sum_{j=1}^p \mu_j f_j \in F\) and \(w := -\sum_{k=1}^q \nu_k g_k \in G\). The relation reads \(v = w\), so \(v \in F \cap G\). Then \(v = \sum_{i=1}^r \alpha_i e_i\) for some \(\alpha_i\). Using freeness of the basis \((e_1, \ldots, e_r, f_1, \ldots, f_p)\) of \(F\): $$ \sum_{i=1}^r \alpha_i e_i = \sum_{i=1}^r \lambda_i e_i + \sum_{j=1}^p \mu_j f_j, $$ gives \(\mu_j = 0\) for all \(j\) and \(\alpha_i = \lambda_i\) for all \(i\). So on the one hand \(w = v = \sum_{i=1}^r \lambda_i e_i\), and on the other \(w = -\sum_{k=1}^q \nu_k g_k\), hence \(\sum_{i=1}^r \lambda_i e_i + \sum_{k=1}^q \nu_k g_k = 0_E\). By freeness of the basis \((e_1, \ldots, e_r, g_1, \ldots, g_q)\) of \(G\), all \(\lambda_i = 0\) and all \(\nu_k = 0\). Hence all coefficients vanish: \(\mathcal{C}\) is free. Step 4 --- count. \(\mathcal{C}\) is a basis of \(F + G\) of cardinal \(r + p + q\). Therefore \(F + G\) is of finite dimension and $$ \dim(F + G) = r + p + q = r + (\dim F - r) + (\dim G - r) = \dim F + \dim G - r = \dim F + \dim G - \dim(F \cap G). $$

By the subspace-dimension theorem, \(F\) is of finite dimension; take a basis \((e_1, \ldots, e_p)\) of \(F\), where \(p = \dim F\). By the « base incomplète » theorem applied in \(E\), complete to a basis \((e_1, \ldots, e_p, e_{p+1}, \ldots, e_n)\) of \(E\), where \(n = \dim E\). Set \(G := \mathrm{Vect}(e_{p+1}, \ldots, e_n)\). Direct sum. If \(w \in F \cap G\): \(w = \sum_{i=1}^p \alpha_i e_i = \sum_{j=p+1}^n \beta_j e_j\), so \(\sum_{i=1}^p \alpha_i e_i - \sum_{j=p+1}^n \beta_j e_j = 0\). By freeness of the basis of \(E\), all \(\alpha_i = 0\) and \(\beta_j = 0\), hence \(w = 0\). Sum is \(E\). Every \(x \in E\) writes \(x = \sum_{i=1}^n \lambda_i e_i = \underbrace{\sum_{i=1}^p \lambda_i e_i}_{\in F} + \underbrace{\sum_{j=p+1}^n \lambda_j e_j}_{\in G}\). So \(E = F \oplus G\). Dimension of \(G\). \(G\) has the basis \((e_{p+1}, \ldots, e_n)\) of cardinal \(n - p\), so \(\dim G = n - p = \dim E - \dim F\). Any other supplement \(G'\) of \(F\) in \(E\) satisfies, by Grassmann, \(\dim E = \dim(F + G') = \dim F + \dim G' - \dim(F \cap G') = \dim F + \dim G' - 0\), hence \(\dim G' = \dim E - \dim F\).

Apply the Grassmann formula \(\dim(F + G) = \dim F + \dim G - \dim(F \cap G)\).

• \((1) + (2) \Rightarrow (3)\). \(F \cap G = \{0\}\) gives \(\dim(F \cap G) = 0\); \(F + G = E\) gives \(\dim(F + G) = \dim E\). Grassmann: \(\dim E = \dim F + \dim G\).
• \((1) + (3) \Rightarrow (2)\). \(\dim(F \cap G) = 0\); Grassmann gives \(\dim(F + G) = \dim F + \dim G = \dim E\). So \(F + G\) is a subspace of \(E\) with \(\dim(F + G) = \dim E\), hence \(F + G = E\) by the subspace-dimension theorem (equality case).
• \((2) + (3) \Rightarrow (1)\). \(\dim(F + G) = \dim E\); Grassmann gives \(\dim(F \cap G) = \dim F + \dim G - \dim E = 0\). Hence \(F \cap G = \{0\}\) (only the zero subspace has dimension \(0\)).

When all three hold, \((1)\) and \((2)\) together say \(E = F \oplus G\) by definition of supplementarity.

Direct application of the « base incomplète » theorem: a basis of \(F\) is in particular a free family of \(E\), and \(E\) has a finite generating family. Complete using the algorithm; the result is a basis of \(E\) whose first \(\dim F\) vectors are the basis of \(F\) we started with --- a basis adapted to \(F\).

Let \((e_1, \ldots, e_p)\) be a basis of \(F\) and \((f_1, \ldots, f_q)\) a basis of \(G\). We show \(\mathcal{B} := (e_1, \ldots, e_p, f_1, \ldots, f_q)\) is a basis of \(E\).

• Generating. Every \(w \in E = F \oplus G\) writes \(w = f + g\) with \(f \in F\), \(g \in G\) (definition of sum). Expand \(f = \sum_{i=1}^p \lambda_i e_i\) in the basis of \(F\) and \(g = \sum_{j=1}^q \mu_j f_j\) in the basis of \(G\). Hence \(w\) is a linear combination of \(\mathcal{B}\).
• Free. Suppose \(\sum_{i=1}^p \lambda_i e_i + \sum_{j=1}^q \mu_j f_j = 0_E\). Set \(f := \sum_{i=1}^p \lambda_i e_i \in F\) and \(g := \sum_{j=1}^q \mu_j f_j \in G\). The relation reads \(f + g = 0_E\). Since the sum is direct (\(F \cap G = \{0\}\)), the decomposition of \(0_E\) as element of \(F\) plus element of \(G\) is unique, namely \(0_E = 0_F + 0_G\). So \(f = 0_E\) and \(g = 0_E\). By freeness of the basis of \(F\), all \(\lambda_i = 0\); by freeness of the basis of \(G\), all \(\mu_j = 0\).

\(\mathcal{B}\) is free and generating: a basis of \(E\). The first \(p\) vectors form a basis of \(F\) and the next \(q\) form a basis of \(G\), so \(\mathcal{B}\) is adapted to the decomposition \(E = F \oplus G\).

Admitted here, proved in Differential equations.

Admitted here, proved in Differential equations.

Admitted here, proved in Recurrent sequences.