galois.FieldArray.characteristic_poly() → Poly

Computes the characteristic polynomial of a finite field element a or a square matrix A.

Returns:

For scalar inputs, the degree-m characteristic polynomial ca(x) of a over GF(p). For square n×n matrix inputs, the degree-n characteristic polynomial cA(x) of A over GF(pm).

Raises:

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

Notes

An element a of GF(pm) has characteristic polynomial ca(x) over GF(p). The characteristic polynomial when evaluated in GF(pm) annihilates a, that is ca(a)=0. In prime fields GF(p), the characteristic polynomial of a is simply ca(x)=x−a.

An n×n matrix A has characteristic polynomial cA(x)=det(xI−A) over GF(pm). The constant coefficient of the characteristic polynomial is det(−A). The xn−1 coefficient of the characteristic polynomial is −Tr(A). The characteristic polynomial annihilates A, that is cA(A)=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(9, order=3^5)

In [3]: poly = a.characteristic_poly(); poly
Out[3]: Poly(x^5 + x^3 + x + 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 + 2α + 2, order=3^5)

In [7]: poly = a.characteristic_poly(); poly
Out[7]: Poly(x^5 + 2x^3 + x^2 + x + 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(α^51, order=3^5)

In [11]: poly = a.characteristic_poly(); poly
Out[11]: Poly(x^5 + 2x^4 + 2x^3 + x^2 + 1, 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 A.

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

In [14]: A = GF.Random((3,3)); A
Out[14]: 
GF([[210, 240,  48],
    [231, 220,  13],
    [ 82, 233, 223]], order=3^5)

In [15]: poly = A.characteristic_poly(); poly
Out[15]: Poly(x^3 + 43x^2 + 171x + 68, 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([[       α^3 + 2α^2 + 2,       2α^4 + 2α^2 + 1,    α^3 + 2α^2 + α + 2],
    [        α^4 + α^2 + 2,       2α^4 + 2α^2 + α,        α^4 + 2α^2 + α],
    [           2α^4 + α^3, 2α^4 + 2α^3 + α^2 + 2,       2α^4 + α^2 + 2α]],
   order=3^5)

In [21]: poly = A.characteristic_poly(); poly
Out[21]: Poly(x^3 + (2α^4 + 2α^3 + α^2 + 1)x^2 + (α^4 + 2α^3 + 2α^2 + 2)x + (α^3 + α^2 + 2), 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([[    0,  α^10,  α^11],
    [α^138, α^173,  α^79],
    [ α^52,  α^63,  α^52]], order=3^5)

In [27]: poly = A.characteristic_poly(); poly
Out[27]: Poly(x^3 + (α^104)x + α^47, 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)