$J$-ideals of matrices

Let $B$ be an $n\times n$-matrix over a principal ideal domain $D$.

For an ideal $J$, the $J$-ideal of $B$ is defined to be $N_J(B) = \{ f\in D[X] \mid f(B) \in M_n(J) \}$.

For a prime element $p$ of $D$ and $t\ge 0$, a $(p^t)$-minimal polynomial of $B$ is a monic polynomial $f\in N_{(p^t)}(B)$ of minimal degree.

This module computes these minimal polynomials.

Let $p$ be a prime element of $D$. Then there is a finite set $\mathcal{S}_p$ of positive integers and monic polynomials $\nu_{ps}$ for $s\in\mathcal{S}_p$ such that for $t\ge 1$,

$$\begin{split}N_{(p^t)}(B) = \mu_BD[X] + p^tD[X] + \sum_{\substack{s\in\mathcal{S}_p \\ s \le b(t) }} p^{\max\{0,t-s\}}\nu_{ps}D[X]\end{split}$$

holds where $b(t) = \min\{r\in \mathcal{S}_p \mid r \ge s\}$. The degree of $\nu_{ps}$ is strictly increasing in $s\in \mathcal{S}_p$ and $\nu_{ps}$ is a $(p^s)$-minimal polynomial. If $t\le \max\mathcal{S}_p$, then the summand $\mu_BD[X]$ can be omitted.

All computations are done by the class ComputeMinimalPolynomials where various intermediate results are cached. It provides the following methods:

• p_minimal_polynomials() computes $\mathcal{S}_p$ and the monic polynomials $\nu_{ps}$.

• null_ideal() determines $N_{(p^t)}(B)$.

• prime_candidates() determines all primes $p$ where $\mathcal{S}_p$ might be non-empty.

• integer_valued_polynomials_generators() determines the generators of the ring $\{f \in K[X] \mid f(B) \in M_n(D)\}$ of integer valued polynomials on $B$.

EXAMPLES:

sage: from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
sage: B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
sage: C = ComputeMinimalPolynomials(B)
sage: C.prime_candidates()
[2, 3, 5]
sage: for t in range(4):
....:     print(C.null_ideal(2^t))
Principal ideal (1) of
    Univariate Polynomial Ring in x over Integer Ring
Ideal (2, x^2 + x) of
    Univariate Polynomial Ring in x over Integer Ring
Ideal (4, x^2 + 3*x + 2) of
    Univariate Polynomial Ring in x over Integer Ring
Ideal (8, x^3 + x^2 - 12*x - 20, 2*x^2 + 6*x + 4) of
    Univariate Polynomial Ring in x over Integer Ring
sage: C.p_minimal_polynomials(2)
{2: x^2 + 3*x + 2}
sage: C.integer_valued_polynomials_generators()
(x^3 + x^2 - 12*x - 20, [1, 1/4*x^2 + 3/4*x + 1/2])

The last output means that

$$\{f \in \QQ[X] \mid f(B) \in M_3(\ZZ)\} = (x^3 + x^2 - 12x - 20)\QQ[X] + \ZZ[X] + \frac{1}{4}(x^2 + 3x + 2) \ZZ[X].$$

Todo

Test code over PIDs other than ZZ.

This requires implementation of frobenius() over more general domains than ZZ.

Additionally, lifting() requires modification or a bug needs fixing, see AskSage Question 35555.

REFERENCES:

[Ris2016], [HR2016]

AUTHORS:

• Clemens Heuberger (2016)

• Roswitha Rissner (2016)

ACKNOWLEDGEMENT:

• Clemens Heuberger is supported by the Austrian Science Fund (FWF): P 24644-N26.

• Roswitha Rissner is supported by the Austrian Science Fund (FWF): P 27816-N26.

Classes and Methods

class sage.matrix.compute_J_ideal.ComputeMinimalPolynomials(B)

Bases: sage.structure.sage_object.SageObject

Create an object for computing $(p^t)$-minimal polynomials and $J$-ideals.

For an ideal $J$ and a square matrix $B$ over a principal ideal domain $D$, the $J$-ideal of $B$ is defined to be $N_J(B) = \{ f\in D[X] \mid f(B) \in M_n(J) \}$.

For a prime element $p$ of $D$ and $t\ge 0$, a $(p^t)$-minimal polynomial of $B$ is a monic polynomial $f\in N_{(p^t)}(B)$ of minimal degree.

The characteristic polynomial of $B$ is denoted by $\chi_B$; $n$ is the size of $B$.

INPUT:

• B – a square matrix over a principal ideal domain $D$

OUTPUT:

An object which allows to call p_minimal_polynomials(), null_ideal() and integer_valued_polynomials_generators().

EXAMPLES:

sage: from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
sage: B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
sage: C = ComputeMinimalPolynomials(B)
sage: C.prime_candidates()
[2, 3, 5]
sage: for t in range(4):
....:     print(C.null_ideal(2^t))
Principal ideal (1) of
    Univariate Polynomial Ring in x over Integer Ring
Ideal (2, x^2 + x) of
    Univariate Polynomial Ring in x over Integer Ring
Ideal (4, x^2 + 3*x + 2) of
    Univariate Polynomial Ring in x over Integer Ring
Ideal (8, x^3 + x^2 - 12*x - 20, 2*x^2 + 6*x + 4) of
    Univariate Polynomial Ring in x over Integer Ring
sage: C.p_minimal_polynomials(2)
{2: x^2 + 3*x + 2}
sage: C.integer_valued_polynomials_generators()
(x^3 + x^2 - 12*x - 20, [1, 1/4*x^2 + 3/4*x + 1/2])

current_nu(p, t, pt_generators, prev_nu)

Compute $(p^t)$-minimal polynomial of $B$.

INPUT:

• p – a prime element of $D$

• t – a positive integer

• pt_generators – a list $(g_1, \ldots, g_s)$ of polynomials in $D[X]$ such that $N_{(p^t)}(B) = (g_1, \ldots, g_s) + pN_{(p^{t-1})}(B)$

• prev_nu – a $(p^{t-1})$-minimal polynomial of $B$

OUTPUT:

A $(p^t)$-minimal polynomial of $B$.

EXAMPLES:

sage: from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
sage: B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
sage: C = ComputeMinimalPolynomials(B)
sage: x = polygen(ZZ, 'x')
sage: nu_1 = x^2 + x
sage: generators_4 = [2*x^2 + 2*x, x^2 + 3*x + 2]
sage: C.current_nu(2, 2, generators_4, nu_1)
x^2 + 3*x + 2

ALGORITHM:

[HR2016], Algorithm 4.

find_monic_replacements(p, t, pt_generators, prev_nu)

Replace possibly non-monic generators of $N_{(p^t)}(B)$ by monic generators.

INPUT:

• p – a prime element of $D$

• t – a non-negative integer

• pt_generators – a list $(g_1, \ldots, g_s)$ of polynomials in $D[X]$ such that $N_{(p^t)}(B) = (g_1, \ldots, g_s) + pN_{(p^{t-1})}(B)$

• prev_nu – a $(p^{t-1})$-minimal polynomial of $B$

OUTPUT:

A list $(h_1, \ldots, h_r)$ of monic polynomials such that $N_{(p^t)}(B) = (h_1, \ldots, h_r) + pN_{(p^{t-1})}(B)$.

EXAMPLES:

sage: from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
sage: B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
sage: C = ComputeMinimalPolynomials(B)
sage: x = polygen(ZZ, 'x')
sage: nu_1 = x^2 + x
sage: generators_4 = [2*x^2 + 2*x, x^2 + 3*x + 2]
sage: C.find_monic_replacements(2, 2, generators_4, nu_1)
[x^2 + 3*x + 2]

ALGORITHM:

[HR2016], Algorithms 2 and 3.

integer_valued_polynomials_generators()

Determine the generators of the ring of integer valued polynomials on $B$.

OUTPUT:

A pair (mu_B, P) where P is a list of polynomials in $K[X]$ such that

$$\{f \in K[X] \mid f(B) \in M_n(D)\} = \mu_B K[X] + \sum_{g\in P} g D[X]$$

where $K$ denotes the fraction field of $D$.

EXAMPLES:

sage: from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
sage: B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
sage: C = ComputeMinimalPolynomials(B)
sage: C.integer_valued_polynomials_generators()
(x^3 + x^2 - 12*x - 20, [1, 1/4*x^2 + 3/4*x + 1/2])

mccoy_column(p, t, nu)

Compute matrix for McCoy’s criterion.

INPUT:

• p – a prime element in $D$

• t – a positive integer

• nu – a $(p^t)$-minimal polynomial of $B$

OUTPUT:

An $(n^2 + 1) \times 1$ matrix $g$ with first entry nu such that $\begin{pmatrix}b& -\chi_B I\end{pmatrix}g \equiv 0\pmod{p^t}$ where $b$ consists of the entries of $\operatorname{adj}(X-B)$.

EXAMPLES:

sage: from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
sage: B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
sage: C = ComputeMinimalPolynomials(B)
sage: x = polygen(ZZ, 'x')
sage: nu_4 = x^2 + 3*x + 2
sage: g = C.mccoy_column(2, 2, nu_4)
sage: b = matrix(9, 1, (x-B).adjugate().list())
sage: M = matrix.block([[b , -B.charpoly(x)*matrix.identity(9)]])
sage: (M*g % 4).is_zero()
True

ALGORITHM:

[HR2016], Algorithm 5.

null_ideal(b=0)

Return the $(b)$-ideal $N_{(b)}(B)=\{f\in D[X] \mid f(B)\in M_n(bD)\}$.

INPUT:

• b – an element of $D$ (default: 0)

OUTPUT:

An ideal in $D[X]$.

EXAMPLES:

sage: from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
sage: B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
sage: C = ComputeMinimalPolynomials(B)
sage: C.null_ideal()
Principal ideal (x^3 + x^2 - 12*x - 20) of
    Univariate Polynomial Ring in x over Integer Ring
sage: C.null_ideal(2)
Ideal (2, x^2 + x) of
    Univariate Polynomial Ring in x over Integer Ring
sage: C.null_ideal(4)
Ideal (4, x^2 + 3*x + 2) of
    Univariate Polynomial Ring in x over Integer Ring
sage: C.null_ideal(8)
Ideal (8, x^3 + x^2 - 12*x - 20, 2*x^2 + 6*x + 4) of
    Univariate Polynomial Ring in x over Integer Ring
sage: C.null_ideal(3)
Ideal (3, x^3 + x^2 - 12*x - 20) of
    Univariate Polynomial Ring in x over Integer Ring
sage: C.null_ideal(6)
Ideal (6, 2*x^3 + 2*x^2 - 24*x - 40, 3*x^2 + 3*x) of
    Univariate Polynomial Ring in x over Integer Ring

p_minimal_polynomials(p, s_max=None)

Compute $(p^s)$-minimal polynomials $\nu_s$ of $B$.

Compute a finite subset $\mathcal{S}$ of the positive integers and $(p^s)$-minimal polynomials $\nu_s$ for $s \in \mathcal{S}$.

For $0 < t \le \max \mathcal{S}$, a $(p^t)$-minimal polynomial is given by $\nu_s$ where $s = \min\{ r \in \mathcal{S} \mid r\ge t \}$. For $t > \max \mathcal{S}$, the minimal polynomial of $B$ is also a $(p^t)$-minimal polynomial.

INPUT:

• p – a prime in $D$

• s_max – a positive integer (default: None); if set, only $(p^s)$-minimal polynomials for s <= s_max are computed (see below for details)

OUTPUT:

A dictionary. Keys are the finite set $\mathcal{S}$, the values are the associated $(p^s)$-minimal polynomials $\nu_s$, $s \in \mathcal{S}$.

Setting s_max only affects the output if s_max is at most $\max\mathcal{S}$ where $\mathcal{S}$ denotes the full set. In that case, only those $\nu_s$ with s <= s_max are returned where s_max is always included even if it is not included in the full set $\mathcal{S}$.

EXAMPLES:

sage: from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
sage: B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
sage: C = ComputeMinimalPolynomials(B)
sage: C.p_minimal_polynomials(2)
{2: x^2 + 3*x + 2}
sage: set_verbose(1)
sage: C = ComputeMinimalPolynomials(B)
sage: C.p_minimal_polynomials(2)
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
------------------------------------------
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
p = 2, t = 1:
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
Result of lifting:
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
F =
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
[x^2 + x]
[      x]
[      0]
[      1]
[      1]
[  x + 1]
[      1]
[      0]
[      0]
[  x + 1]
verbose 1 (...: compute_J_ideal.py, current_nu)
------------------------------------------
verbose 1 (...: compute_J_ideal.py, current_nu)
(x^2 + x)
verbose 1 (...: compute_J_ideal.py, current_nu)
Generators with (p^t)-generating property:
verbose 1 (...: compute_J_ideal.py, current_nu)
[x^2 + x]
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
nu = x^2 + x
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
corresponding columns for G
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
[x^2 + x]
[  x + 2]
[      0]
[      1]
[      1]
[  x - 1]
[     -1]
[     10]
[      0]
[  x + 1]
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
------------------------------------------
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
p = 2, t = 2:
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
Result of lifting:
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
F =
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
[  2*x^2 + 2*x x^2 + 3*x + 2]
[          2*x         x + 4]
[            0             0]
[            2             1]
[            2             1]
[      2*x + 2         x + 1]
[            2            -1]
[            0            10]
[            0             0]
[      2*x + 2         x + 3]
verbose 1 (...: compute_J_ideal.py, current_nu)
------------------------------------------
verbose 1 (...: compute_J_ideal.py, current_nu)
(2*x^2 + 2*x, x^2 + 3*x + 2)
verbose 1 (...: compute_J_ideal.py, current_nu)
Generators with (p^t)-generating property:
verbose 1 (...: compute_J_ideal.py, current_nu)
[x^2 + 3*x + 2]
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
nu = x^2 + 3*x + 2
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
corresponding columns for G
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
[x^2 + 3*x + 2]
[        x + 4]
[            0]
[            1]
[            1]
[        x + 1]
[           -1]
[           10]
[            0]
[        x + 3]
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
------------------------------------------
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
p = 2, t = 3:
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
Result of lifting:
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
F =
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
[x^3 + 7*x^2 + 6*x x^3 + 3*x^2 + 2*x]
[        x^2 + 8*x         x^2 + 4*x]
[                0                 0]
[                x             x + 4]
[            x + 4                 x]
[    x^2 + 5*x + 4           x^2 + x]
[           -x + 4                -x]
[             10*x              10*x]
[                0                 0]
[        x^2 + 7*x     x^2 + 3*x + 4]
verbose 1 (...: compute_J_ideal.py, current_nu)
------------------------------------------
verbose 1 (...: compute_J_ideal.py, current_nu)
(x^3 + 7*x^2 + 6*x, x^3 + 3*x^2 + 2*x)
verbose 1 (...: compute_J_ideal.py, current_nu)
Generators with (p^t)-generating property:
verbose 1 (...: compute_J_ideal.py, current_nu)
...
verbose 1 (...: compute_J_ideal.py, current_nu)
[x^3 + 3*x^2 + 2*x]
verbose 1 (...: compute_J_ideal.py, p_minimal_polynomials)
nu = x^3 + 3*x^2 + 2*x
{2: x^2 + 3*x + 2}
sage: set_verbose(0)
sage: C.p_minimal_polynomials(2, s_max=1)
{1: x^2 + x}
sage: C.p_minimal_polynomials(2, s_max=2)
{2: x^2 + 3*x + 2}
sage: C.p_minimal_polynomials(2, s_max=3)
{2: x^2 + 3*x + 2}

ALGORITHM:

[HR2016], Algorithm 5.

prime_candidates()

Determine those primes $p$ where $\mu_B$ might not be a $(p)$-minimal polynomial.

OUTPUT:

A list of primes.

EXAMPLES:

sage: from sage.matrix.compute_J_ideal import ComputeMinimalPolynomials
sage: B = matrix(ZZ, [[1, 0, 1], [1, -2, -1], [10, 0, 0]])
sage: C = ComputeMinimalPolynomials(B)
sage: C.prime_candidates()
[2, 3, 5]
sage: C.p_minimal_polynomials(2)
{2: x^2 + 3*x + 2}
sage: C.p_minimal_polynomials(3)
{}
sage: C.p_minimal_polynomials(5)
{}

This means that $3$ and $5$ were candidates, but actually, $\mu_B$ turns out to be a $(3)$-minimal polynomial and a $(5)$-minimal polynomial.

sage.matrix.compute_J_ideal.lifting(p, t, A, G)

Compute generators of $\{f \in D[X]^d \mid Af \equiv 0 \pmod{p^{t}}\}$ given generators of $\{f\in D[X]^d \mid Af \equiv 0\pmod{p^{t-1}}\}$.

INPUT:

• p – a prime element of some principal ideal domain $D$

• t – a non-negative integer

• A – a $c\times d$ matrix over $D[X]$

• G – a matrix over $D[X]$. The columns of $\begin{pmatrix}p^{t-1}I& G\end{pmatrix}$ are generators of $\{ f\in D[X]^d \mid Af \equiv 0\pmod{p^{t-1}}\}$; can be set to None if t is zero

OUTPUT:

A matrix $F$ over $D[X]$ such that the columns of $\begin{pmatrix}p^tI&F&pG\end{pmatrix}$ are generators of $\{ f\in D[X]^d \mid Af \equiv 0\pmod{p^t}\}$.

EXAMPLES:

sage: from sage.matrix.compute_J_ideal import lifting
sage: X = polygen(ZZ, 'X')
sage: A = matrix([[1, X], [2*X, X^2]])
sage: G0 = lifting(5, 0, A, None)
sage: G1 = lifting(5, 1, A, G0); G1
[]
sage: (A*G1 % 5).is_zero()
True
sage: A = matrix([[1, X, X^2], [2*X, X^2, 3*X^3]])
sage: G0 = lifting(5, 0, A, None)
sage: G1 = lifting(5, 1, A, G0); G1
[3*X^2]
[    X]
[    1]
sage: (A*G1 % 5).is_zero()
True
sage: G2 = lifting(5, 2, A, G1); G2
[15*X^2 23*X^2]
[   5*X      X]
[     5      1]
sage: (A*G2 % 25).is_zero()
True
sage: lifting(5, 10, A, G1)
Traceback (most recent call last):
...
ValueError: A*G not zero mod 5^9

ALGORITHM:

[HR2016], Algorithm 1.

sage.matrix.compute_J_ideal.p_part(f, p)

Compute the $p$-part of a polynomial.

INPUT:

• f – a polynomial over $D$

• p – a prime in $D$

OUTPUT:

A polynomial $g$ such that $\deg g \le \deg f$ and all non-zero coefficients of $f - p g$ are not divisible by $p$.

EXAMPLES:

sage: from sage.matrix.compute_J_ideal import p_part
sage: X = polygen(ZZ, 'X')
sage: f = X^3 + 5*X + 25
sage: g = p_part(f, 5); g
X + 5
sage: f - 5*g
X^3