Choose the representation that makes the dominant operation cheap
An element of a number field can be held as a polynomial in θ, as the matrix of multiplication by that element, as the vector of its images under all embeddings, or as its minimal polynomial. Multiplication is cheapest in the conjugate representation, trace and norm fall out of the matrix representation, and exactness lives in the standard representation. Practical systems keep more than one and convert as needed.
Learning objectives
- Describe each of the four representations and its natural operations.
- Convert between representations and state the cost of each conversion.
- Choose a representation for a given computational profile.
- Explain why the minimal polynomial is not a complete representation.
Section 01The four representations
| Representation | Data | Cheap operations | Expensive operations |
|---|---|---|---|
| Standard | Rational vector of coefficients against 1, θ, …, θn−1 | Addition, scalar multiplication, exactness | Multiplication needs reduction modulo T; inversion needs extended GCD |
| Matrix (regular) | n×n rational matrix of multiplication by α | Trace, norm, characteristic polynomial, inversion | n2 storage; multiplication is matrix multiplication |
| Conjugate vector | The n complex values σi(α) | Multiplication and division are componentwise | Not exact; addition is fine but recovery of exact coefficients needs precision |
| Minimal polynomial | The monic irreducible polynomial of α | Degree, conjugates, algebraic identity | Does not identify which root — incomplete on its own |
Two distinct elements of the same field — for instance √2 and −√2 — share a minimal polynomial. It identifies an element only up to conjugacy, so it must be paired with a root selection (a numerical approximation, or an expression in θ) to specify the element.
Section 02The regular representation
Multiplication by α is a ℚ-linear map on K. Its matrix Mα against a chosen basis is the regular representation, and it converts field questions into linear algebra.
The map α ↦ Mα is a ring homomorphism, so products and inverses correspond to matrix products and inverses. Inversion in particular is just a linear solve, which is often more convenient than the extended Euclidean algorithm on polynomials.
The characteristic polynomial of Mα is the minimal polynomial raised to the power [K : ℚ(α)]. They coincide exactly when α generates the whole field — which is the test for whether α is a primitive element.
Section 03Conversions
- For j = 0, …, n−1, compute α · θj as a polynomial in θ.
- Reduce each product modulo the defining polynomial T. This is the only step that needs polynomial arithmetic.
- Write each reduced product as a coefficient vector; these vectors are the columns of Mα.
- Return Mα.
| From | To | Cost | Method |
|---|---|---|---|
| Standard | Matrix | O(n2) | Multiply by each basis element and reduce |
| Matrix | Standard | O(n) | Read the first column |
| Standard | Conjugate | O(n2) evaluations | Evaluate at each root |
| Conjugate | Standard | O(n2) plus precision | Interpolate, then round — requires certified precision |
| Standard | Minimal polynomial | O(n3) | Characteristic polynomial of the matrix, then remove repeated factors |
Section 04Choosing a representation
- What dominates the computation?
- Ring arithmetic on integers Integral basis coordinates — integer vectors, exact, and directly compatible with Hermite normal form.
- Many multiplications Conjugate vectors — componentwise, but only with a certified precision budget and an exact recovery step.
- Traces and norms Matrix representation — both are single linear algebra operations.
- Field membership and identity Standard representation — exact comparison of rational vectors.
Where a numerical representation is used for speed, the exact standard or integral-basis form should remain the source of truth, with the numerical form treated as a cache. Any result derived numerically must be confirmed exactly before it is recorded.
ReferenceFrequently asked questions
Why not always use the matrix representation?
Because it costs n² storage per element rather than n, and multiplication becomes matrix multiplication. It is the right choice when traces, norms or inverses dominate, and the wrong one when many elements must simply be stored and added.
How much precision do conjugate vectors need?
Enough that the exact coefficients can be recovered by rounding after interpolation. That depends on the size of the coefficients and on the conditioning of the root set, so the precision must be derived from an explicit bound rather than fixed in advance.
Can an element be represented against the integral basis instead of powers of theta?
Yes, and for algebraic integers it should be — the coordinates are then integers rather than rationals with a common denominator. All ideal and module arithmetic uses this representation.
NavigateContinue in this stream
Curated next steps from this page. The site also surfaces algorithmically related reading below.
ProvenanceSources and further reading
This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.