Activate

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 – optional boolean. If True, only the permanent is computed (might be faster).
• var – a variable name

EXAMPLES:

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

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]

An example over $\QQ$:

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

An example with polynomial coefficients:

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

A usage of the var argument:

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

ALGORITHM:

The permanent $perm(A)$ of a $n \times n$ matrix $A$ is the coefficient of the $x_1 x_2 \ldots 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, \ldots, \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, \ldots, \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, \ldots, \eta_n)$ or $p(\eta_{i_1}, \ldots, \eta_{i_k})$ if we want to emphasize that some monomials in the $\eta_i$ are missing.

Introduce an “integration” operation $\langle p \rangle$ 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 $\langle \eta_1 \rangle^2 = 1$ while $\langle \eta_1^2 \rangle = 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

$$\langle p_1 p_2 \rangle = 1 + 4t + 3t^2$$

In this formalism, the permanent is just

$$perm(A) = \langle \prod_{i=1}^n \sum_{j=1}^n A_{ij} \eta_j \rangle$$

A useful property of $\langle . \rangle$ which makes this algorithm efficient for band matrices is the following: let $p_1(\eta_1, \ldots, \eta_n)$ and $p_2(\eta_j, \ldots, \eta_n)$ be polynomials in $R[t]$ where $j \ge 1$. Then one has

$$\langle p_1(\eta_1, \ldots, \eta_n) p_2 \rangle = \langle p_1(1, \ldots, 1, \eta_j, \ldots, \eta_n) p_2 \rangle$$

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 \leq 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) = \left\langle \prod_{i=1}^m \left(1 + t \sum_{j=1}^n A_{ij} \eta_j\right) \right\rangle$$

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, \ldots, \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, \ldots, \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} \ldots \eta_{i_k}$ is associated the key $2^{i_1} + \ldots + 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$ – an 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: 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}

sage.matrix.matrix_misc.row_iterator(A)