# $$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:

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:

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: 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