galois.FieldArray.characteristic_poly

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¶

https://en.wikipedia.org/wiki/Characteristic_polynomial

Examples¶

The characteristic polynomial of the element \(a\).

Integer Polynomial Power

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

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

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

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

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

Integer Polynomial Power

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

In [14]: A = GF.Random((3,3)); A
Out[14]: 
GF([[ 38,  39, 214],
    [171, 114,  33],
    [ 52, 144, 145]], order=3^5)

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

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

# The x^n-1 coefficient is -Tr(A)
In [17]: poly.coeffs[1] == -np.trace(A)
Out[17]: np.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([[2α^4 + α^3 + 2α^2 + 2α + 2,                   2α^2 + 1,
                              0],
    [              2α^4 + α + 1,            α^3 + 2α^2 + 2α,
          2α^4 + 2α^3 + α^2 + 2],
    [      2α^4 + α^3 + α^2 + 1,       α^4 + α^3 + α^2 + 2α,
                2α^4 + 2α^2 + 2]], order=3^5)

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

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

# The x^n-1 coefficient is -Tr(A)
In [23]: poly.coeffs[1] == -np.trace(A)
Out[23]: np.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([[  α^8, α^155, α^103],
    [α^172,   α^2,  α^31],
    [α^161, α^114, α^196]], order=3^5)

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

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

# The x^n-1 coefficient is -Tr(A)
In [29]: poly.coeffs[1] == -np.trace(A)
Out[29]: np.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)