Return the polynomial of the sums of permanental minors of A.
INPUT:
The polynomial of the sums of permanental minors is
where is the
-th permanental minor of
(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 [ButPer]. Its complexity is where
and
are the number of rows and columns of
. Moreover, if
is a banded
matrix with width
, that is
for
and
,
then the complexity of the algorithm is
.
INPUT:
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 :
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
of a
matrix
is the coefficient of the
monomial in
Evaluating this product one can neglect
, that is
can be considered to be nilpotent of order
.
To formalize this procedure, consider the algebra
where the
are commuting, nilpotent of order
(i.e.
). Formally it is the quotient ring of the polynomial ring in
quotiented by the ideal generated by the
.
We will mostly consider the ring
of polynomials over
. We denote a generic element of
by
or
if we want to emphasize that some monomials in the
are missing.
Introduce an “integration” operation
over
and
consisting in the sum of the coefficients of the non-vanishing monomials in
(i.e. the result of setting all variables
to
). Let us emphasize that this is not a morphism of algebras as
while
!
Let us consider an example of computation. Let
and
. Then
and
In this formalism, the permanent is just
A useful property of
which makes this algorithm efficient for band matrices is the following: let
and
be polynomials in
where
. Then one has
where
are replaced by
in
. Informally, we can “integrate” these variables before performing the product. More generally, if a monomial
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
matrix with
. The sum of permanental `k`-minors of `A` is
where the sum is over the
-subsets
of rows and
-subsets
of columns and
is the submatrix obtained from
by keeping only the rows
and columns
. Of course
and note that
is just the sum of all entries of the matrix.
The generating function of these sums of permanental minors is
In fact the
coefficient of
corresponds to choosing
rows of
;
is associated to the i-th column; nilpotency avoids having twice the same column in a product of
‘s.
For more details, see the article [ButPer].
From a technical point of view, the product in
is implemented as a subroutine in prm_mul(). The indices of the rows and columns actually start at
, so the variables are
. Polynomials are represented in dictionary form: to a variable
is associated the key
(or in Python 1 << i). The keys associated to products are obtained by considering the development in base
: to the monomial
is associated the key
. So the product
corresponds to the key
while
has key
. In particular all operations on monomials are implemented via bitwise operations on the keys.
REFERENCES:
[ButPer] | P. Butera and M. Pernici “Sums of permanental minors using Grassmann algebra”, Arxiv 1406.5337 |
Return the product of p1 and p2, putting free variables in
mask_free to .
This function is mainly use as a subroutine of permanental_minor_polynomial().
INPUT:
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}
x.__init__(...) initializes x; see help(type(x)) for signature
This function computes a weak Popov form of a matrix over a rational
function field , for
a field.
INPUT:
- matrix
- if True, rows of output matrix
are sorted so degree (= the maximum of the degrees of the elements in the row) increases monotonically, and otherwise degrees decrease.
OUTPUT:
A 3-tuple consisting of two matrices over
and a list
of integers:
is invertible over
. These matrices satisfy the relation
.
EXAMPLES:
The routine expects matrices over the rational function field, but other examples below show how one can provide matrices over the ring of polynomials (whose quotient field is the rational function field).
sage: R.<t> = GF(3)['t']
sage: K = FractionField(R)
sage: import sage.matrix.matrix_misc
sage: sage.matrix.matrix_misc.weak_popov_form(matrix([[(t-1)^2/t],[(t-1)]]))
(
[ 0] [ t 2*t + 1]
[(2*t + 1)/t], [ 1 2], [-Infinity, 0]
)
NOTES:
See docstring for weak_popov_form method of matrices for more information.