The lower bound is Omega(n^2 lg n), but waiting for an algorithm (if there is one). Ref: Ran Raz - http://dl.acm.org/citation.cfm?id=944299 (similar complexity for Matrix Inversion due to the relationship between matrix inversion and multiplication, ref Introduction to Algorithms, 1st ed, pp 762-765, wrote the proof here http://amundtveit.info/publications/2003/ComplexityOfMatrixI...)