# Computational complexity of finding determinants

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.

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)$$.
• I can't see a way to go faster than $\mathcal{O}(n^2)$, so Gaussian elimination seems pretty good. Jan 17, 2019 at 2:59