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.
Best Answer
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.