Linear Algebra Algorithms
Operations on Subspaces and Modules
Sum, intersection and quotient of subspaces, and how the analogous operations on modules over the integers require normal forms.
Engineering / MathematicsLinear Algebra Algorithms2 min readKV-MATH-0535
Sums, intersections and quotients are the everyday operations on subspaces. Over a field they are elimination problems. Over the integers the same operations describe modules, and the answers require normal forms rather than echelon forms.
Over a field
| Operation | Method | Cost |
|---|---|---|
| Sum | Concatenate bases and reduce | One elimination |
| Intersection | Kernel of the stacked system | One elimination |
| Quotient | Supplement the subspace; quotient coordinates are the supplement coordinates | One elimination |
| Membership | Solve a linear system | One elimination |
Over the integers
A finitely generated subgroup of a free abelian group is again free, but a spanning set is not a basis and the distinction matters. The Hermite normal form provides a canonical basis, which is what makes the operations well defined.
- Sum of modules
- Concatenate generating sets and compute the Hermite normal form. The result is a canonical basis of the sum.
- Intersection
- Computed as a kernel, then normalised. More expensive than the sum because it needs a kernel computation over the integers.
- Quotient
- The Smith normal form of the inclusion matrix gives the invariant factors, hence the structure of the quotient group.
- Index
- The determinant of the transition matrix, when both modules have the same rank.
Modules with denominators
Ideals of a number field are frequently represented as an integer matrix divided by a common denominator. Operations then proceed on the numerator matrices with denominators tracked separately and cleared to a common value before combining.
Canonical forms matter
The representation used throughout the number field streams is described in module representation by Hermite normal form.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 2.3.3-2.3.4. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.