Permanent/Examples/Matrix whose Entries are Product of Row and Column Indices
Jump to navigation
Jump to search
Example of Permanent
The square matrix of the form:
- $\begin{pmatrix}
1 \times 1 & 1 \times 2 & \cdots & 1 \times m \\ 2 \times 1 & 2 \times 2 & \cdots & 2 \times m \\ \vdots & \vdots & \ddots & \vdots \\ m \times 1 & m \times 2 & \cdots & m \times m \end{pmatrix}$
has a permanent of $\left({n!}\right)^3$.
Proof
There are $n!$ terms in a permanent.
By its structure, each one of these has one element from each row multitplied by one element from each column.
Thus each term of the permanent consists of:
- $\left({1 \times 2 \times \cdots \times n}\right) \times \left({1 \times 2 \times \cdots \times n}\right)$
in some order, that is:
- $\left({n!}\right)^2$
As has been stated, there are $n!$ of these.
Thus the permanent of this matrix is $n! \left({n!}\right)^2$.
Hence the result.
$\blacksquare$
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.5$: Permutations and Factorials: Exercise $15$