Miscellaneous matrix functions

sage.matrix.matrix_misc.permanental_minor_polynomial(A, permanent_only=False, var='t', prec=None)

Return the polynomial of the sums of permanental minors of A.

INPUT:

• A – a matrix

• permanent_only – if True, return only the permanent of $A$

• var – name of the polynomial variable

• prec – if prec is not None, truncate the polynomial at precision $prec$

The polynomial of the sums of permanental minors is

$$\sum _{i=0}^{min(nrows,ncols)}{p}_i(A)x^i$$

where $p_i(A)$ is the $i$-th permanental minor of $A$ (that can also be obtained through the method permanental_minor() via A.permanental_minor(i)).

The algorithm implemented by that function has been developed by P. Butera and M. Pernici, see [BP2015]. Its complexity is $O(2^n{m}^{2}n)$ where $m$ and $n$ are the number of rows and columns of $A$. Moreover, if $A$ is a banded matrix with width $w$, that is $A_{ij}=0$ for $|i-j|>w$ and $w<n/2$, then the complexity of the algorithm is $O(4^w(w+1)n^2)$.

INPUT:

• A – matrix

• permanent_only – boolean (default: False); if True, only the permanent is computed (might be faster)

• var – a variable name

EXAMPLES:

Sage

sage: from sage.matrix.matrix_misc import permanental_minor_polynomial
sage: m = matrix([[1,1],[1,2]])
sage: permanental_minor_polynomial(m)
3*t^2 + 5*t + 1
sage: permanental_minor_polynomial(m, permanent_only=True)
3
sage: permanental_minor_polynomial(m, prec=2)
5*t + 1

Python

>>> from sage.all import *
>>> from sage.matrix.matrix_misc import permanental_minor_polynomial
>>> m = matrix([[Integer(1),Integer(1)],[Integer(1),Integer(2)]])
>>> permanental_minor_polynomial(m)
3*t^2 + 5*t + 1
>>> permanental_minor_polynomial(m, permanent_only=True)
3
>>> permanental_minor_polynomial(m, prec=Integer(2))
5*t + 1

Sage Live

from sage.matrix.matrix_misc import permanental_minor_polynomial
m = matrix([[1,1],[1,2]])
permanental_minor_polynomial(m)
permanental_minor_polynomial(m, permanent_only=True)
permanental_minor_polynomial(m, prec=2)

Sage

sage: M = MatrixSpace(ZZ,4,4)
sage: A = M([1,0,1,0,1,0,1,0,1,0,10,10,1,0,1,1])
sage: permanental_minor_polynomial(A)
84*t^3 + 114*t^2 + 28*t + 1
sage: [A.permanental_minor(i) for i in range(5)]
[1, 28, 114, 84, 0]

Python

>>> from sage.all import *
>>> M = MatrixSpace(ZZ,Integer(4),Integer(4))
>>> A = M([Integer(1),Integer(0),Integer(1),Integer(0),Integer(1),Integer(0),Integer(1),Integer(0),Integer(1),Integer(0),Integer(10),Integer(10),Integer(1),Integer(0),Integer(1),Integer(1)])
>>> permanental_minor_polynomial(A)
84*t^3 + 114*t^2 + 28*t + 1
>>> [A.permanental_minor(i) for i in range(Integer(5))]
[1, 28, 114, 84, 0]

Sage Live

M = MatrixSpace(ZZ,4,4)
A = M([1,0,1,0,1,0,1,0,1,0,10,10,1,0,1,1])
permanental_minor_polynomial(A)
[A.permanental_minor(i) for i in range(5)]

An example over $\mathbf{Q}$:

Sage

sage: M = MatrixSpace(QQ,2,2)
sage: A = M([1/5,2/7,3/2,4/5])
sage: permanental_minor_polynomial(A, True)
103/175

Python

>>> from sage.all import *
>>> M = MatrixSpace(QQ,Integer(2),Integer(2))
>>> A = M([Integer(1)/Integer(5),Integer(2)/Integer(7),Integer(3)/Integer(2),Integer(4)/Integer(5)])
>>> permanental_minor_polynomial(A, True)
103/175

Sage Live

M = MatrixSpace(QQ,2,2)
A = M([1/5,2/7,3/2,4/5])
permanental_minor_polynomial(A, True)

An example with polynomial coefficients:

Sage

sage: R.<a> = PolynomialRing(ZZ)
sage: A = MatrixSpace(R,2)([[a,1], [a,a+1]])
sage: permanental_minor_polynomial(A, True)
a^2 + 2*a

Python

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, names=('a',)); (a,) = R._first_ngens(1)
>>> A = MatrixSpace(R,Integer(2))([[a,Integer(1)], [a,a+Integer(1)]])
>>> permanental_minor_polynomial(A, True)
a^2 + 2*a

Sage Live

R.<a> = PolynomialRing(ZZ)
A = MatrixSpace(R,2)([[a,1], [a,a+1]])
permanental_minor_polynomial(A, True)

A usage of the var argument:

Sage

sage: m = matrix(ZZ,4,[0,1,2,3,1,2,3,0,2,3,0,1,3,0,1,2])
sage: permanental_minor_polynomial(m, var='x')
164*x^4 + 384*x^3 + 172*x^2 + 24*x + 1

Python

>>> from sage.all import *
>>> m = matrix(ZZ,Integer(4),[Integer(0),Integer(1),Integer(2),Integer(3),Integer(1),Integer(2),Integer(3),Integer(0),Integer(2),Integer(3),Integer(0),Integer(1),Integer(3),Integer(0),Integer(1),Integer(2)])
>>> permanental_minor_polynomial(m, var='x')
164*x^4 + 384*x^3 + 172*x^2 + 24*x + 1

Sage Live

m = matrix(ZZ,4,[0,1,2,3,1,2,3,0,2,3,0,1,3,0,1,2])
permanental_minor_polynomial(m, var='x')

ALGORITHM:

The permanent $perm(A)$ of a $n\times n$ matrix $A$ is the coefficient of the $x_1{x}_2\dots x_n$ monomial in

$$\prod _{i=1}^n\left(\sum _{j=1}^n{A}_{ij}{x}_j\right)$$

Evaluating this product one can neglect $x_i^2$, that is $x_i$ can be considered to be nilpotent of order $2$.

To formalize this procedure, consider the algebra $R=K[{\eta }_1,{\eta }_2,\dots ,{\eta }_n]$ where the ${\eta }_i$ are commuting, nilpotent of order $2$ (i.e. ${\eta }_i^2=0$). Formally it is the quotient ring of the polynomial ring in ${\eta }_1,{\eta }_2,\dots ,{\eta }_n$ quotiented by the ideal generated by the ${\eta }_i^2$.

We will mostly consider the ring $R[t]$ of polynomials over $R$. We denote a generic element of $R[t]$ by $p({\eta }_1,\dots ,{\eta }_n)$ or $p({\eta }_{i_1},\dots ,{\eta }_{i_k})$ if we want to emphasize that some monomials in the ${\eta }_i$ are missing.

Introduce an “integration” operation $⟨p⟩$ over $R$ and $R[t]$ consisting in the sum of the coefficients of the non-vanishing monomials in ${\eta }_i$ (i.e. the result of setting all variables ${\eta }_i$ to $1$). Let us emphasize that this is not a morphism of algebras as $⟨{\eta }_1{⟩}^2=1$ while $⟨{\eta }_1^2⟩=0$!

Let us consider an example of computation. Let $p_1=1+t{\eta }_1+t{\eta }_2$ and $p_2=1+t{\eta }_1+t{\eta }_3$. Then

$$p_1{p}_2=1+2t{\eta }_1+t({\eta }_2+{\eta }_3)+t^2({\eta }_1{\eta }_2+{\eta }_1{\eta }_3+{\eta }_2{\eta }_3)$$

and

$$⟨p_1{p}_2⟩=1+4t+3t^2$$

In this formalism, the permanent is just

$$perm(A)=⟨\prod _{i=1}^n\sum _{j=1}^n{A}_{ij}{\eta }_j⟩$$

A useful property of $⟨.⟩$ which makes this algorithm efficient for band matrices is the following: let $p_1({\eta }_1,\dots ,{\eta }_n)$ and $p_2({\eta }_j,\dots ,{\eta }_n)$ be polynomials in $R[t]$ where $j\ge 1$. Then one has

$$⟨p_1({\eta }_1,\dots ,{\eta }_n)p_2⟩=⟨p_1(1,\dots ,1,{\eta }_j,\dots ,{\eta }_n)p_2⟩$$

where ${\eta }_1,..,{\eta }_{j-1}$ are replaced by $1$ in $p_1$. Informally, we can “integrate” these variables before performing the product. More generally, if a monomial ${\eta }_i$ is missing in one of the terms of a product of two terms, then it can be integrated in the other term.

Now let us consider an $m\times n$ matrix with $m\le n$. The sum of permanental `k`-minors of `A` is

$$perm(A,k)=\sum _{r,c}perm(A_{r,c})$$

where the sum is over the $k$-subsets $r$ of rows and $k$-subsets $c$ of columns and $A_{r,c}$ is the submatrix obtained from $A$ by keeping only the rows $r$ and columns $c$. Of course $perm(A,min(m,n))=perm(A)$ and note that $perm(A,1)$ is just the sum of all entries of the matrix.

The generating function of these sums of permanental minors is

$$g(t)=⟨\prod _{i=1}^m(1+t\sum _{j=1}^n{A}_{ij}{\eta }_j)⟩$$

In fact the $t^k$ coefficient of $g(t)$ corresponds to choosing $k$ rows of $A$; ${\eta }_i$ is associated to the $i$-th column; nilpotency avoids having twice the same column in a product of $A$’s.

For more details, see the article [BP2015].

From a technical point of view, the product in $K[{\eta }_1,\dots ,{\eta }_n][t]$ is implemented as a subroutine in prm_mul(). The indices of the rows and columns actually start at $0$, so the variables are ${\eta }_0,\dots ,{\eta }_{n-1}$. Polynomials are represented in dictionary form: to a variable ${\eta }_i$ is associated the key $2^i$ (or in Python 1 << i). The keys associated to products are obtained by considering the development in base $2$: to the monomial ${\eta }_{i_1}\dots {\eta }_{i_k}$ is associated the key $2^{i_1}+\dots +2^{i_k}$. So the product ${\eta }_1{\eta }_2$ corresponds to the key $6=(110{)}_2$ while ${\eta }_0{\eta }_3$ has key $9=(1001{)}_2$. In particular all operations on monomials are implemented via bitwise operations on the keys.

sage.matrix.matrix_misc.prm_mul(p1, p2, mask_free, prec)

Return the product of p1 and p2, putting free variables in mask_free to $1$.

This function is mainly use as a subroutine of permanental_minor_polynomial().

INPUT:

• $p1,p2$ – polynomials as dictionaries

• mask_free – integer mask that give the list of free variables (the $i$-th variable is free if the $i$-th bit of mask_free is $1$)

• prec – if prec is not None, truncate the product at precision prec

EXAMPLES:

Sage

sage: from sage.matrix.matrix_misc import prm_mul
sage: t = polygen(ZZ, 't')
sage: p1 = {0: 1, 1: t, 4: t}
sage: p2 = {0: 1, 1: t, 2: t}
sage: prm_mul(p1, p2, 1, None)
{0: 2*t + 1, 2: t^2 + t, 4: t^2 + t, 6: t^2}

Python

>>> from sage.all import *
>>> from sage.matrix.matrix_misc import prm_mul
>>> t = polygen(ZZ, 't')
>>> p1 = {Integer(0): Integer(1), Integer(1): t, Integer(4): t}
>>> p2 = {Integer(0): Integer(1), Integer(1): t, Integer(2): t}
>>> prm_mul(p1, p2, Integer(1), None)
{0: 2*t + 1, 2: t^2 + t, 4: t^2 + t, 6: t^2}

Sage Live

from sage.matrix.matrix_misc import prm_mul
t = polygen(ZZ, 't')
p1 = {0: 1, 1: t, 4: t}
p2 = {0: 1, 1: t, 2: t}
prm_mul(p1, p2, 1, None)

sage.matrix.matrix_misc.row_iterator(A)

Make live