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 [ButPer]. 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 [ButPer].

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.

REFERENCES:

[ButPer]P. Butera and M. Pernici “Sums of permanental minors using Grassmann algebra”, Arxiv 1406.5337
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)

x.__init__(...) initializes x; see help(type(x)) for signature

sage.matrix.matrix_misc.weak_popov_form(M, ascend=True)

This function computes a weak Popov form of a matrix over a rational function field k(x), for k a field.

INPUT:

  • M - matrix
  • ascend - if True, rows of output matrix W 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 (W,N,d) consisting of two matrices over k(x) and a list of integers:

  1. W - matrix giving a weak the Popov form of M
  2. N - matrix representing row operations used to transform M to W
  3. d - degree of respective columns of W; the degree of a column is the maximum of the degree of its elements

N is invertible over k(x). These matrices satisfy the relation N*M = W.

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.

Previous topic

Matrices over an arbitrary ring

Next topic

Abstract base class for matrices

This Page