(why) does the number of rows in a matrix have to be less than or equal to the number of columns to compute a permanent?

344 Views Asked by At

I'm trying to learn about computing the permanents of rectangular matrices, and everywhere I go it seems to say that in order to have a permanent or compute a permanent of a rectangular matrix efficiently, a little confused about which one, the number of rows needs to be less than or equal to the number of columns in the matrix. However, especially in light of the generating function interpretation of permanents I don't see why this has to be, can someone explain this to me please.

1

There are 1 best solutions below

0
On

The key idea is that for $k=\min(m,n)$, the permanent is the sum of all possible products of $k$ elements, with no two of the $k$ selected elements from any row or column.

Hence, as I noted in my comment, the calculation wouldn't be any different for the transpose, so without loss of generality, we can assume $m\le n$.