galois.FieldArray.characteristic_poly() Poly

Computes the characteristic polynomial of a finite field element $$a$$ or a square matrix $$\mathbf{A}$$.

Returns:

For scalar inputs, the degree-$$m$$ characteristic polynomial $$c_a(x)$$ of $$a$$ over $$\mathrm{GF}(p)$$. For square $$n \times n$$ matrix inputs, the degree-$$n$$ characteristic polynomial $$c_A(x)$$ of $$\mathbf{A}$$ over $$\mathrm{GF}(p^m)$$.

Raises:

ValueError – If the array is not a single finite field element (scalar 0-D array) or a square $$n \times n$$ matrix (2-D array).

Notes

An element $$a$$ of $$\mathrm{GF}(p^m)$$ has characteristic polynomial $$c_a(x)$$ over $$\mathrm{GF}(p)$$. The characteristic polynomial when evaluated in $$\mathrm{GF}(p^m)$$ annihilates $$a$$, that is $$c_a(a) = 0$$. In prime fields $$\mathrm{GF}(p)$$, the characteristic polynomial of $$a$$ is simply $$c_a(x) = x - a$$.

An $$n \times n$$ matrix $$\mathbf{A}$$ has characteristic polynomial $$c_A(x) = \textrm{det}(x\mathbf{I} - \mathbf{A})$$ over $$\mathrm{GF}(p^m)$$. The constant coefficient of the characteristic polynomial is $$\textrm{det}(-\mathbf{A})$$. The $$x^{n-1}$$ coefficient of the characteristic polynomial is $$-\textrm{Tr}(\mathbf{A})$$. The characteristic polynomial annihilates $$\mathbf{A}$$, that is $$c_A(\mathbf{A}) = \mathbf{0}$$.

References

Examples

The characteristic polynomial of the element $$a$$.

In [1]: GF = galois.GF(3**5)

In [2]: a = GF.Random(); a
Out[2]: GF(227, order=3^5)

In [3]: poly = a.characteristic_poly(); poly
Out[3]: Poly(x^5 + x^3 + x^2 + 2x + 2, GF(3))

# The characteristic polynomial annihilates a
In [4]: poly(a, field=GF)
Out[4]: GF(0, order=3^5)

In [5]: GF = galois.GF(3**5, repr="poly")

In [6]: a = GF.Random(); a
Out[6]: GF(2α^4 + 2, order=3^5)

In [7]: poly = a.characteristic_poly(); poly
Out[7]: Poly(x^5 + 2x^3 + 2x^2 + 2, GF(3))

# The characteristic polynomial annihilates a
In [8]: poly(a, field=GF)
Out[8]: GF(0, order=3^5)

In [9]: GF = galois.GF(3**5, repr="power")

In [10]: a = GF.Random(); a
Out[10]: GF(α^118, order=3^5)

In [11]: poly = a.characteristic_poly(); poly
Out[11]: Poly(x^5 + x^4 + 2, GF(3))

# The characteristic polynomial annihilates a
In [12]: poly(a, field=GF)
Out[12]: GF(0, order=3^5)


The characteristic polynomial of the square matrix $$\mathbf{A}$$.

In [13]: GF = galois.GF(3**5)

In [14]: A = GF.Random((3,3)); A
Out[14]:
GF([[ 61, 199, 108],
[195,  75,  25],
[123,  52,  59]], order=3^5)

In [15]: poly = A.characteristic_poly(); poly
Out[15]: Poly(x^3 + 15x^2 + 231x + 130, GF(3^5))

# The x^0 coefficient is det(-A)
In [16]: poly.coeffs[-1] == np.linalg.det(-A)
Out[16]: True

# The x^n-1 coefficient is -Tr(A)
In [17]: poly.coeffs[1] == -np.trace(A)
Out[17]: True

# The characteristic polynomial annihilates the matrix A
In [18]: poly(A, elementwise=False)
Out[18]:
GF([[0, 0, 0],
[0, 0, 0],
[0, 0, 0]], order=3^5)

In [19]: GF = galois.GF(3**5, repr="poly")

In [20]: A = GF.Random((3,3)); A
Out[20]:
GF([[          α^4 + α^3 + 2α^2,             2α^4 + α^3 + 1,
α^4 + 2α^3 + 2α^2],
[               α^3 + α + 1,                2α^4 + 2α^2,
α^4 + α + 1],
[              α^2 + 2α + 1,                    α^3 + 1,
2α^4 + 2α^3 + α^2 + 2α + 1]], order=3^5)

In [21]: poly = A.characteristic_poly(); poly
Out[21]: Poly(x^3 + (α^4 + α^2 + α + 2)x^2 + (2α^3 + α + 2)x + (α^4 + α^3 + α^2 + α + 1), GF(3^5))

# The x^0 coefficient is det(-A)
In [22]: poly.coeffs[-1] == np.linalg.det(-A)
Out[22]: True

# The x^n-1 coefficient is -Tr(A)
In [23]: poly.coeffs[1] == -np.trace(A)
Out[23]: True

# The characteristic polynomial annihilates the matrix A
In [24]: poly(A, elementwise=False)
Out[24]:
GF([[0, 0, 0],
[0, 0, 0],
[0, 0, 0]], order=3^5)

In [25]: GF = galois.GF(3**5, repr="power")

In [26]: A = GF.Random((3,3)); A
Out[26]:
GF([[ α^49,  α^46,  α^43],
[ α^80, α^121,  α^68],
[α^215, α^135, α^211]], order=3^5)

In [27]: poly = A.characteristic_poly(); poly
Out[27]: Poly(x^3 + (α^55)x^2 + (α^214)x + α^55, GF(3^5))

# The x^0 coefficient is det(-A)
In [28]: poly.coeffs[-1] == np.linalg.det(-A)
Out[28]: True

# The x^n-1 coefficient is -Tr(A)
In [29]: poly.coeffs[1] == -np.trace(A)
Out[29]: True

# The characteristic polynomial annihilates the matrix A
In [30]: poly(A, elementwise=False)
Out[30]:
GF([[0, 0, 0],
[0, 0, 0],
[0, 0, 0]], order=3^5)