In applications one often encounters very large matrices that barely fit in computer memory, if at all. Naturally one wishes to represent those matrices as compactly as possible. Sometimes one even sacrifices accuracy for compactness, as in L-BFGS for example.
On the other hand, often enough the linear problem naturally appears with matrices that can be presented in a relatively compact form, either with band matrices or Toeplitz matrices, etc.
Let's call an $n\times n$ matrix presentation "compact" if it requires no more than $O(n \log^{const} n)$ entries (that's the "quasilinear" rule of thumb for trackability of large problems). Is there a way to tell that a family of matrices is presentable in a "compact" form? And, if it is, what would be a computationally feasible algorithm to compute that presentation?
Or, to put it differently, has something like Kolmogorov complexity been studied for matrices? Here by "Kolmogorov complexity" one may understand a map $M_{n\times n}\to \mathbb{N}$ mapping a matrix to the length of its shortest presentation.
This is different from sparsity of matrices, as evident from compact yet dense Toeplitz matrices.
