@article{BKL-Some-Computational-Problems-In-Linear-Algebra-As-Hard-As-Matrix-Multiplication,
Title = {Some computational problems in linear algebra as hard as matrix multiplication},
Author = {Peter Bürgisser and Marek Karpinski and Thomas Lickteig},
Pages = {131-155},
Year = {1991},
Doi = {10.1007/BF01272518},
Journal = {Comp. Compl.},
Volume = {1},
Number = {2},
Abstract = {We define the complexity of a computational problem given by a relation using the model of computation trees together with the Ostrowski complexity measure. Natural examples from linear algebra are: $KER_n$: Compute a basis of the kernel for a given $n\times n$ matrix, $OGB_n$: Find an invertible matrix that transforms a given symmetric $n\times n$ matrix (quadratic form) into diagonal form, $SPR_n$: Find a sparse representation of a given $n\times n$ matrix. To such a sequence of problems we assign an exponent similarly as for matrix multiplication. For the complexity of the above problems we prove relative lower bounds of the form $a M_n - b$ and absolute lower bounds $d n^2$, where $M_n$ denotes the complexity of matrix multiplication and $a$, $b$, $d$ are suitably chosen constants. We show that the exponents of the problem sequences KER, OGB, SPR are the same as the exponent of matrix multiplication.},
Url = {http://link.springer.com/article/10.1007%2FBF01272518},
Url2 = {http://dx.doi.org/10.1007/BF01272518}
}