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 $nXn$.

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. to $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 1 but it is not very clear (either Algorithm or its complexity)

  • $\begingroup$ Anyone please? I don't think there is anything wrong with the Query.. $\endgroup$ – J.Doe Jun 14 '18 at 10:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.