Engineering/Mathematics/Abstract algebra

Modules, Vector Spaces and Matrices

Linear algebra over a finite field is not a variation on the real case — it is the same theory with exact arithmetic and no numerical error. That makes Gaussian elimination a decision procedure rather than an approximation, and it is the final step of every sieve-based factoring run.

Structural theory
Linear algebra
Sieve back-end
≈16 min read
Feeds factoring and coding

O(n³)Elimination costField operations to reduce an n × n system — exact, with no stability analysis required over a finite field.

dimWell definedEvery basis of a finite-dimensional vector space has the same size, so dimension is an invariant, not a choice.

rank + nullity= nThe rank–nullity identity is what guarantees a sieve matrix with more rows than columns has a non-trivial kernel.

F₂Working fieldSieve linear algebra runs over F₂, where a row is a bit vector and elimination is XOR.

Executive summary

A module is a vector space over a ring rather than a field. Dropping invertibility of scalars costs a great deal: modules need not have bases, and dimension need not be defined. Over a field everything is recovered, and the resulting theory — bases, dimension, rank, kernel — is exactly the machinery that finite-field algorithms need.

Two practical themes run through this page. First, over a finite field there is no rounding, so elimination is exact and pivoting is a matter of finding any non-zero entry rather than the largest one. Second, the matrices that arise in factoring and discrete-log algorithms are enormous and sparse, which rules out dense elimination and motivates the iterative methods treated elsewhere in the library.

GeneralModule over R

Additive group with scalar multiplication. May have no basis; e.g. ℤ_n as a ℤ-module.

SpecialVector space over F

Every module over a field has a basis, and all bases have the same size.

MapLinear transformation

Determined by its action on a basis; represented by a matrix once bases are fixed.

AlgorithmGaussian elimination

One O(n³) procedure solves systems, computes rank, kernel, inverse and determinant.

Contents

Modules and why fields are different

Definition D1

Module over a commutative ring

An R-module is an abelian group M with a scalar multiplication R × M → M satisfying distributivity, associativity (rs)m = r(sm) and 1m = m. When R is a field the module is called a vector space.

What survives and what fails
Property	Over a field	Over a general ring	Example of failure
Every module has a basis	Yes	No	ℤ₆ as a ℤ-module has no linearly independent element
All bases have equal size	Yes	Yes for commutative R ≠ 0	—
Submodule of free is free	Yes	Only over a PID	Ideals of ℤ[X] can need two generators
Quotient by a submodule	Yes	Yes	—
Rank is well defined	Yes	Only over a domain	Torsion elements have no rank

Modules over a PID admit a structure theorem — free part plus torsion — which specialises to the classification of finite abelian groups when R = ℤ.

A finite abelian group is exactly a ℤ-module, so the structure theorem for finite abelian groups and the theory of finitely generated modules over a PID are the same result. Similarly, F_q^k is a k-dimensional vector space over F_q, which is where its element count comes from.

Contents

Independence, bases and dimension

Theorem T1

Dimension is well defined

In a vector space V over a field F, any linearly independent set can be extended to a basis and any spanning set contains a basis. All bases of a finite-dimensional V have the same cardinality, written dim_F V. Consequently |V| = |F|^{dim V} when F is finite.

Exchange lemma. The proof rests on being able to trade a basis vector for an independent one, which requires dividing by a non-zero scalar — the step that fails over a general ring.
Coordinates. Fixing a basis identifies V with Fⁿ. All computation happens in coordinates; the basis-free language exists to keep proofs honest about what depends on that choice.
Counting corollary. The number of ordered bases of F_qⁿ is ∏_i=0ⁿ⁻¹(qⁿ − qⁱ), which is also the order of the general linear group GL_n(F_q). A random n × n matrix over F_q is invertible with probability ∏_i=1ⁿ(1 − q⁻ⁱ), which tends to about 0.289 for q = 2.

The 0.289 constant matters

Over F₂ a random square matrix is singular with probability roughly 71%. Algorithms that need an invertible random matrix — or that need a dependency to exist — must be analysed with this in mind, and sieve algorithms deliberately collect several more relations than unknowns so that the kernel is non-trivial with overwhelming probability.

Contents

Matrices as linear maps

Once bases are fixed, an F-linear map ρ : Fⁿ → F^m is a matrix and composition is matrix multiplication. The invariants of the map appear as invariants of the matrix.

Invariants and what they answer
Invariant	Definition	Question it answers
Rank	dimension of the image	How many independent equations does the system really contain?
Kernel (null space)	{v : Av = 0}	What are the solutions of the homogeneous system?
Rank–nullity	rank + dim ker = n	More columns than rank ⇒ a non-trivial kernel exists
Determinant	product of pivots up to sign	Is a square matrix invertible?
Characteristic polynomial	det(XI − A)	Eigenstructure; its minimal-polynomial factor drives Wiedemann's algorithm

Over a finite field these are all computed exactly; there is no notion of an ill-conditioned matrix and no error propagation.

Theorem T2

Solvability of a linear system

Ax = b has a solution if and only if rank(A) = rank([A ∣ b]). When solvable, the solution set is a coset x₀ + ker A, so it has exactly |F|^{dim ker A} elements over a finite field F.

Contents

Gaussian elimination and its applications

Gaussian elimination over a field

input: A ∈ F^{m×n}
r ← 0
for each column c = 1..n:
find a row i > r with A[i][c] ≠ 0; if none, continue
r ← r+1; swap rows i and r; scale row r by A[r][c]^{-1}
for each row j ≠ r: A[j] ← A[j] − A[j][c]·A[r]
output: reduced row echelon form; r = rank(A)

O(n²m) field operations; O(n³) for a square system. Over F₂ each row operation is a word-parallel XOR, giving a constant-factor speed-up of 64 on a 64-bit machine.

Solve a system

Row reduce [A ∣ b]; read off a particular solution and a kernel basis from the free columns.

Compute a kernel basis

Each non-pivot column yields one kernel vector. This is the step that turns sieve relations into a factorization.

Invert a matrix

Row reduce [A ∣ I]; the right block becomes A⁻¹ when the left becomes I.

Compute rank and determinant

Rank is the pivot count; the determinant is the product of pivots times the sign of the row swaps.

Find minimal polynomials

Reduce the matrix whose rows are the coordinate vectors of 1, α, α², … to find the first dependency.

Decode linear codes

Syndrome computation and the parity-check equations of a linear code are elimination problems over F_q.

Dense elimination does not scale to sieve matrices

A record-sized factoring run produces a matrix with hundreds of millions of rows and columns, but only a few dozen non-zero entries per row. Dense O(n³) elimination is impossible at that size, and would also destroy sparsity through fill-in. Production systems use structured Gaussian elimination for an initial reduction, then an iterative kernel method — Wiedemann or block Lanczos — whose cost is proportional to the number of non-zero entries.

Contents

Working over a finite field in practice

Implementation notes by field
Field	Row representation	Elimination step	Typical use
F₂	packed bit vector	XOR of words	Sieve kernels, binary codes, XL-style algebraic attacks
F_p, word-size p	array of machine integers	multiply–subtract with lazy reduction	Multi-modular exact linear algebra
F_2⁸	byte array with log tables	table-driven multiply	Reed–Solomon erasure coding
ℚ via modular images	residues modulo several primes	solve mod each prime, then CRT and rational reconstruction	Exact rational linear algebra without coefficient growth

The last row is the standard remedy for intermediate expression swell: exact rational elimination can blow coefficient sizes up exponentially, whereas modular images stay bounded.

No pivoting for stability. Over a finite field any non-zero pivot is as good as any other. Pivot choice is driven by sparsity — pick the pivot that causes the least fill-in.
Failure is informative. If elimination over ℤ_n for composite n hits a non-zero, non-invertible pivot, the gcd of that entry with n is a proper factor — occasionally a useful accident.
Rank over a random modulus. Reducing an integer matrix modulo a random prime preserves rank with high probability, which gives a cheap probabilistic rank test before committing to exact work.

Contents

Quick reference and FAQ

Linear algebra facts
Fact	Statement
Dimension	All bases of a finite-dimensional space have the same size
Rank–nullity	rank A + dim ker A = n (columns)
Solvability	Ax = b solvable ⟺ rank A = rank[A ∣ b]
Solution count	\|F\|^{dim ker A} over a finite field
More columns than rows	A non-trivial kernel always exists
\|GL_n(F_q)\|	∏_i=0ⁿ⁻¹(qⁿ − qⁱ)
Elimination cost	O(n³) field operations, dense
Field size	\|V\| = \|F\|^{dim V}

Why does linear algebra over ℤ need different tools?

ℤ is not a field, so you cannot divide by a pivot. The right normal form is the Hermite or Smith normal form, computed with unimodular row operations. These are the tools for lattice problems and for the structure theorem over a PID.

Is Strassen-style fast matrix multiplication worth using here?

Rarely. Sub-cubic algorithms help only for large dense matrices, and the matrices in number-theoretic algorithms are either small or sparse. Over F₂, the Method of Four Russians is the practical dense speed-up, giving O(n³/log n).

How large a kernel do sieve algorithms need?

One non-zero kernel vector gives a candidate congruence of squares, which succeeds in factoring with probability at least 1/2. Collecting a few dozen extra relations yields a kernel of dimension several, so a handful of independent attempts is available from a single run.

Where do modules rather than vector spaces genuinely appear?

In lattice-based algorithms, where the objects are ℤ-modules inside ℝⁿ, and in the structure theory of finite abelian groups, which is the classification of finitely generated ℤ-modules.

Contents

References and further reading

V. Shoup, A Computational Introduction to Number Theory and Algebra, Cambridge University Press, 2005 — Chapters 14 and 15.
S. Lang, Algebra, 3rd ed., Springer, 2002 — Chapter III on modules.
J. von zur Gathen and J. Gerhard, Modern Computer Algebra, 3rd ed., Cambridge, 2013 — §25 on linear algebra over rings.
P. L. Montgomery, 'A block Lanczos algorithm for finding dependencies over GF(2)', EUROCRYPT '95, LNCS 921, 106–120.

KEVOS® Knowledge LibraryEngineering → MathematicsTaxonomy ID: ENG-MATHPage ID: modules-vector-spaces-and-matricesReview cycle: annual

Modules, Vector Spaces and Matrices

Executive summary

Modules and why fields are different

Module over a commutative ring

Independence, bases and dimension

Dimension is well defined

Matrices as linear maps

Solvability of a linear system

Gaussian elimination and its applications

Solve a system

Compute a kernel basis

Invert a matrix

Compute rank and determinant

Find minimal polynomials

Decode linear codes

Working over a finite field in practice

Quick reference and FAQ

References and further reading

Continue learning

KEVOS Intelligence

Executive summary

Modules and why fields are different

Module over a commutative ring

Independence, bases and dimension

Dimension is well defined

Matrices as linear maps

Solvability of a linear system

Gaussian elimination and its applications

Solve a system

Compute a kernel basis

Invert a matrix

Compute rank and determinant

Find minimal polynomials

Decode linear codes

Working over a finite field in practice

Quick reference and FAQ

Related pages in this library

References and further reading

Continue learning