# Time Complexity - Reducing Square Matrix to Diagonal Matrix (using Gaussian Row Elimination)

Given: A Square Matrix where each entry is an integer (either positive or negative). The magnitude of each integer entry is at most $m$ bits. The size of the Square matrix is $n \times n$.

Objective: Reduce the Square Matrix to a Diagonal Matrix form using Gaussian Row Elimination.

Query: What is the most efficient algorithm and its time complexity for the above?

Comment: Most sources discuss the number of operations but not the total computational complexity. The obvious method is to use the text book method of row elimination. But I am assuming in the worst case, it is possible for the intermediate matrix entries to blow up exponentially in their size (w.r.t. $m$). Thus, I am not clear.

Can someone help with the most efficient algorithm to achieve the above and its time complexity? (a clear reference to a textbook/source where that algorithm as well as its complexity is derived would be equally great).

P.S. I was suggested this link Link but it is not very clear (either Algorithm or its complexity)

There are more efficient methods that are built upon using block matrices and randomized matrices however the following method is Gaussian Elimination or the LU Decomposition. Given $$A \in \mathbb{C}^{m \times m}$$ The elimination process is equivalent to the following $$L_{m-1}\cdots L_{2}L_{1}A = U$$ Here we set $$L = L_{1}^{-1}L_{2}^{-1}\cdots L_{m-1}^{-1} \implies A= LU$$ This yields the following algorithm. with an operation count of $$\approx \frac{2}{3}m^{3} \textrm{flops}$$