Linear Algebra Algorithms
Inverse Image and Supplementation of Subspaces
Solving for preimages of a subspace, extending an independent set to a basis, and the linear algebra primitives these support.
Engineering / MathematicsLinear Algebra Algorithms2 min readKV-MATH-0534
Beyond kernel and image, two further primitives recur: finding the preimage of a subspace under a linear map, and extending an independent set to a full basis. Both reduce to elimination, but the reductions are worth stating explicitly.
Inverse image
Given a linear map and a subspace of the target, the preimage is the set of vectors mapped into that subspace. It always contains the kernel, and is computed by solving a combined system.
Computing an inverse image
- Form the combined matrixPlace the map's matrix alongside a basis of the target subspace.
- Compute the kernelFind the kernel of the combined system.
- ProjectThe components corresponding to the source space give the preimage basis.
Supplementation
A supplement of a subspace is any complement: a subspace intersecting it trivially and spanning the whole space together with it. Supplements are not unique, and any algorithm returns one of many.
Extending to a basis
- Reduce the given basisRow reduce the vectors spanning the subspace and note the pivot positions.
- Select standard vectorsTake the standard basis vectors corresponding to non-pivot positions.
- VerifyThe combined set has full rank by construction.
Intersection of subspaces
The intersection of two subspaces is computed as a kernel: stack bases of the two subspaces, find the linear dependencies, and read off the intersection from the coefficients on one side.
Where these are used
Supplementation appears in ring of multipliers computation and in algebra splitting, where a subalgebra must be extended to a full basis. Inverse images appear whenever an ideal is pulled back along a ring map, which is the core operation in Buchmann-Lenstra.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 2.3.2. 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.