Engineering / Mathematics — Modules, Vector Spaces and Matrices
Computing Rank, Kernel and Image
Extracting rank, kernel basis and image basis from an echelon form, and the applications to polynomial factorisation.
Executive summary
Once a matrix is in echelon form, rank, kernel and image are all read off directly. The kernel basis comes from the free columns, one basis vector per free column.
Berlekamp's factorisation algorithm is exactly a kernel computation, which is why this machinery appears in a number theory collection.
Learning objectives
- Extract rank, kernel and image from echelon form.
- Construct an explicit kernel basis.
- Connect the computation to polynomial factorisation.
01Reading off the invariants
Rank
The number of pivots in the echelon form.
Image basis
The pivot columns of the original matrix, not of the reduced one.
Kernel dimension
The number of free columns, equal to n minus the rank.
Kernel basis
One vector per free column: set that free variable to 1, all other free variables to 0, and back-substitute for the pivot variables.
rank + nullity = number of columns02Constructing the kernel basis
Kernel basis from reduced echelon form
matrix A over a fielda basis for the kernel of A- Reduce A to reduced row echelon form, recording pivot columns.
- Identify the free columns as those without a pivot.
- For each free column j:
- Create a vector v with vⱼ = 1 and all other free coordinates 0.
- For each pivot row, set the corresponding pivot coordinate to the negative of the entry in column j.
- Add v to the basis.
- Return the collection of vectors.
O(n³) for the reduction, O(n²) per basis vectorThe resulting vectors are independent by construction, since each has a 1 in a coordinate where the others have 0, and there are exactly as many as the nullity — so they form a basis.
03Application to polynomial factorisation
Berlekamp's algorithm factors a squarefree polynomial over a finite field by computing the kernel of a specific linear map, the Berlekamp map.
Berlekamp's key fact
For a squarefree polynomial f over F_q, the dimension of the kernel of the map v ↦ v^q − v on F_q[X]/(f) equals the number of irreducible factors of f.
So the number of factors is a nullity, computable by elimination before any factor is found. Each non-trivial kernel element then splits f by taking gcds.
Count factors first
The rank computation reveals how many factors exist, which tells the algorithm when it is finished.
Split using kernel elements
Each kernel element v gives gcd(f, v − c) for constants c, and these gcds separate the factors.
Cost
Building the matrix dominates; the elimination is on a matrix of size the degree of f.
04Frequently asked questions
Why take image basis columns from the original matrix?
Because row operations change the column space. They preserve which sets of columns are dependent, so the pivot positions identify an independent set, but the actual vectors must come from the original.
Is the kernel basis unique?
No. Any basis of the kernel is valid, and different elimination orders give different bases. The construction above gives a canonical one relative to the choice of free columns.
How large is the Berlekamp matrix?
Its size is the degree of the polynomial, so factoring a degree-n polynomial costs O(n³) field operations for the elimination. For high degrees the Cantor-Zassenhaus method is preferred, being roughly quadratic.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 328-331.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.