Math Problems Vault

Problem 5.4.1

(1)(2)(3)

Find the permanent of the matrix

?

(1)

$\begin{pmatrix} a & b \\ c & d \end{pmatrix}$ ;

(2)

$4 \times 4$ in which $k = 0,1,2,3,4$ diagonal entries are zeros and all the other (including the off-diagonal) entries are ones;

(3)

$n \times n$ with zeros on the diagonal and ones off the diagonal.

Remark.

?

The permanent of a square matrix $A = (a_{ij})$ of size $n \times n$ is defined by the formula

\operatorname {Per}(A) := \sum _{\sigma \in \Sigma _{n}} \prod _{i=1}^{n} a_{i,\sigma (i)},

where $\Sigma_{n}$ is the set of all permutations of an $n$ -element set.

Problem 5.4.2

Find the permanent of the $m \times n$ matrix consisting entirely of ones.

?

Remark.

?

A submatrix of a given matrix is a matrix obtained from it by deleting some number of rows and columns. The permanent of a rectangular matrix $A$ is defined as the sum of the permanents of all its square submatrices of maximal size. Or, as a formula, for $m < n$

\operatorname {Per}(A) := \sum _{\sigma } \prod _{i=1}^{m} a_{i,\sigma (i)},

where the sum is taken over all $m$ -element arrangements without repetition of the numbers from 1 to $n$ . For $m > n$ we set $\operatorname {Per}(A) := \operatorname {Per}(A^{T})$ .

Problem 5.4.3

(1)(2)

?

(1)

The permanent does not change under a permutation of the rows.

(2)

Row expansion formula. If $m \leqslant n$ , then for every $i$

\operatorname {Per}(A) = \sum _{j=1}^{n} a_{ij}\operatorname {Per}(A_{ij}),

where $A_{ij}$ is the matrix obtained from the original one by deleting the $i$ -th row and the $j$ -th column.

Problem 5.4.4

(1)(2)

?

(1)

The permanent of an $n \times n$ matrix of zeros and ones equals zero if and only if it has a zero $s \times t$ submatrix with $s+t = n+1$ .

(2)

For any $m \leqslant n$ , the permanent of a rectangular $m \times n$ matrix of zeros and ones equals the number of SDRs (Sec. 5.3) of the system of $m$ subsets of the set $\left\{ 1,\ldots ,n\right\}$ determined by the rows of this matrix.