0
$\begingroup$

What is the computational complexity of finding the determinant of a matrix in this form? \begin{bmatrix} x_{1,1} & x_{1,2} & x_{1,3} & \dots & x_{1,n-1} & x_{1,n} \\ x_{2,1} & x_{2,2} & x_{2,3} & \dots & x_{2,n-1} & x_{2,n}\\ 0 & x_{3,2} & x_{3,3} & \dots & x_{3,n-1} & x_{3,n}\\ 0 & 0 & x_{4,3} & \dots & x_{4,n-1} & x_{4,n}\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \dots & x_{n,n-1}& x_{n,n} \end{bmatrix}

In regular matrices this tends to be $O(n^3)$ but I think using row reduction to get a triangle matrix would be much easier. To be clear, the matrix looks like an upper triangular matrix, except it is off by one diagonal. Also all entries in the matrix are positive integers.

$\endgroup$

1 Answer 1

1
$\begingroup$

Yep, this is going to be $\mathcal{O}(n^2)$ by row reduction as you said.

You need to do one elementary row operation to remove the $(2,1)$ entry, and now rows 2 and 3 both have $0$ as a first element, so another row operation removes the $(3,2)$ entry, and so forth. This will be $n-1$ row operations, at a total cost of $\mathcal{O}(n^2)$.

Note, however, that numerical stability may be an issue with Gaussian elimination versus decompositions. This won't be the case with integers, as long as you keep everything as rational numbers.

$\endgroup$
2
  • $\begingroup$ Would that be the most efficient method we have? $\endgroup$
    – Nimish
    Jan 17, 2019 at 2:57
  • $\begingroup$ I can't see a way to go faster than $\mathcal{O}(n^2)$, so Gaussian elimination seems pretty good. $\endgroup$
    – obscurans
    Jan 17, 2019 at 2:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .