2
$\begingroup$

Let $A$ be an $n\times n$ matrix, show that computing the determinant of $A$ requires at most $O(n^3)$ operations (addition, multiplication, etc).

We know that $PA=LU$, and I have already proved that the diagonal entries of a upper(or lower) triangular matrix is equal to its determinant. So $\det(A) =\det(P^{-1}LU)$. So I know $L, U$ need $n$, and for $LU$, it requires $n$.

But how can I say $P^{-1}$ requires $n$? Or is this wrong? Thank you.

$\endgroup$
  • $\begingroup$ What matrix is P? $\endgroup$ – mathreadler May 15 '17 at 22:38
  • $\begingroup$ What matrix is $L$ and $U$? $\endgroup$ – tomasz May 15 '17 at 22:39
  • $\begingroup$ Traditionally, $L$ and $U$ represent lower-triangular and upper-triangular matrices, respectively. See en.wikipedia.org/wiki/LU_decomposition $\endgroup$ – G Tony Jacobs May 15 '17 at 22:40
  • 1
    $\begingroup$ $L$ is a lower triangular matrix, $U$ an upper triangular matrix and $P$ a permutation matrix that grants the existence of the LU decomposition. $\endgroup$ – Oussama Boussif May 15 '17 at 22:40
  • $\begingroup$ $P$ is the permutation matrix, $L,U$ are lower triangular and upper triangular. $\endgroup$ – RRRR May 15 '17 at 22:41
5
$\begingroup$

The easy way to demonstrate that determinant can be done in $O(n^3)$ operations is to use the Gauss-Jordan elimination algorithm with full pivoting, multiplying the pivot elements used (including the remaining element at the end) to get the determinant.

Each step takes $O(n^2)$ operations for the row eliminations, plus $O(n^2)$ for determining the right pivot, plus $O(n)$ for row-swapping, normalization of the pivot row, and other cruft; the sum is still $O(n^2)$. There needs to be $n$ such pivot operations, giving a net complexity of $O(n^3)$.

Actually, you can do much better than that. The Strassen algorithm was the first such one found. It depends on repeatedly dividing the problem into two smaller matrices, and noting that it takes only seven wisely chosen multiplications to multiply two $2\times 2$ matrices; the net complexity for multiplication, inversion, and determinant becomes $O(n^{\log_2 7})$. The Coppersmith-Winograd algorithm has a complexity of better than $O(n^{2.376})$ and there are also slightly better ones than that.

$\endgroup$
  • $\begingroup$ Why do you say $O(n^2)$ for row-swapping? $\endgroup$ – RRRR May 15 '17 at 23:27
  • $\begingroup$ Yes, the row-swapping and pivot row operations are $O(n)$, I wrote $o(n^2)$ meaning smaller than $n^2$ (note the small-o notation used). I will change this to make it clearer.. $\endgroup$ – Mark Fischler May 16 '17 at 15:34
1
$\begingroup$

If you can show (or are allowed to assume that) the LU decomposition can be done in at most $O(n^3)$, then just use $$\det(LU) = \det(L)\det(U)$$ And then remains $n-1$ multiplications calculating each determinant.

(Just multiply together diagonal entries, which is guaranteed to equal the determinant for a triangular matrix as the eigenvalues must be the same as the diagonal entries for such a matrix.)

$\endgroup$
  • $\begingroup$ How can I show $LU$ decomposition can be done at most $O(n^3)$? $\endgroup$ – RRRR May 15 '17 at 23:10

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.