1
$\begingroup$

Let $\mathbf{P}$ be a permutation matrix (i.e. a matrix that is all zeros except for a single one in each row). Is there an efficient algorithm for computing the determinant of such a matrix?

$\endgroup$
3
  • 1
    $\begingroup$ Isn't the determinant of a permutation always either plus or minus one? $\endgroup$ Sep 23 '21 at 17:52
  • 1
    $\begingroup$ Yes, and the question is which one is it. $\endgroup$ Sep 23 '21 at 17:54
  • 3
    $\begingroup$ So that means you want to compute the "parity of a permutation". It exceeds my knowledge to say how that is best done, but it can't be very difficult: In the worst case, you have to do an LU decomposition on a sparse 0-1 matrix and read the determinant as the product of the diagonal of either $L$ or $U$. But it turns out that other people seem to have even cheaper algorithms: stackoverflow.com/questions/20702782/… $\endgroup$ Sep 23 '21 at 19:29
2
$\begingroup$

If you have a linear description of the permutation vector then you can solve it in O(n) time. What you have to do is to compute the size of the cycles in the permutations. From the sizes $s_j$ you compute $\sum_{i=1}^p (s_i-1)$. If that sum is odd, then you get a $1$ for determinant, otherwise a $-1$. The algorithm for computing cycle sizes is pretty simple. You just maintain a visited vector to skip entries visited, and you iterate through the permutation, and for each unvisited vector, you jump into permutation till you find the current element, while marking as visited all the places.

For example if you have $p = [1,0,2,4,5,3]$ you will get $3$ cycles: ${0,1}$, ${2}$ and ${3,4,5}$. Sizes are $2,1,3$. The computed sum is $9$ and the determinant is $-1$.

The issue comes when you do not have a description of the permutation matrix in a vector form (linear size form). If what you have is actually a matrix, than you can't avoid running in $O(n^2)$ time, since you have o read the matrix anyway. However, you don't have to compute any reduction on the matrix, like Gaussian elimination or LU decomposition. Those procedures are designed for dense matrices when you have no idea about the values. There are two ways. First one is to use the previous solution by reducing the matrix to a permutation vector. This works of course and is again straightforward.

There is however another solution, which is still in quadratic time, since you have to read the matrix, but it pass only a single time through matrix. The idea is derived from how matrix determinants are computed using cofactors. If you choose any row or column, the determinant is the sum of the chosen row or column elements multiplied by their cofactors. A cofactor is $-1$ if the row and column index of the element is even, $1$ otherwise, multiplied by the element value, multiplied by the determinant of minor (matrix without row and column where the current element is. More details here: Laplace expansion. This algorithm is useless for dense matrices since is factorial in time. But it is interesting that for permutation matrices it works fine. The idea follows the next rationale: the cofactor expansion produces in fact a single term (since all other values are $0$), so at each iteration one compute have to have correctly the sign. This can be easily done with a maintained visited vector and switching values between $-1$ and $1$. A little attention is required but the algorithm computes the determinant while it is reading the matrix, which should be much faster than the first variant. If the iteration is properly oriented (it takes into account how the matrix is stored in memory) the reading of the matrix should be aligned and the result should be as fast as possible for an O(n^2).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.