Linear Algebra Algorithms
Kernel and Image of a General Matrix
Computing kernel and image bases for rectangular matrices over a field, and why the integer analogue is a different problem.
Engineering / MathematicsLinear Algebra Algorithms2 min readKV-MATH-0533
Kernel and image are the two basic subspaces attached to a matrix. Over a field both fall directly out of row reduction. Over the integers the same words describe a genuinely harder problem.
Over a field
Kernel and image over a field
- ReduceRow reduce to echelon form, tracking column swaps.
- Identify pivotsPivot columns of the original matrix form a basis of the image.
- Free variablesEach non-pivot column gives one kernel basis vector.
- Back-substituteSet the free variable to one, others to zero, and solve for the pivot variables.
The integer case is different
Over the integers, the kernel of a matrix is a lattice rather than a vector space, and the interesting question is a basis for that lattice — not merely a spanning set.
| Question | Over a field | Over the integers |
|---|---|---|
| Kernel | Row reduction | Requires LLL or HNF |
| Image | Pivot columns | A module; needs Hermite normal form |
| Basis quality | Not an issue | Entries can explode; reduction needed |
| Solution existence | Rank condition | Divisibility conditions as well |
Applications
- Berlekamp factorisation
- The kernel of the Frobenius map minus the identity gives the splitting subalgebra — see Berlekamp.
- Radical computation
- The radical of an order modulo p is a kernel — see radical computation.
- Relation lattices
- The kernel of a relation matrix over the integers gives the relations among ideal classes.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 2.3.1. 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.