# 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.

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)#