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](https://en.wikipedia.org/wiki/Limited-memory_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](https://en.wikipedia.org/wiki/Band_matrix) or [Toeplitz matrices](https://en.wikipedia.org/wiki/Toeplitz_matrix), 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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Sparse_matrix) of matrices, as evident from compact yet dense Toeplitz matrices.



Kolmogorov complexity for matrices
[Kolmogorov’s complexity for positive definite matrices](http://www.sciencedirect.com/science/article/pii/S0024379501003548)



> 
> Based on Kolmogorov’s idea, complexity of positive definite matrices
>  with respect to a unit vector is defined. We show that the range of
>  the complexity coincides with the logarithm of its spectrum and the
>  order induced by the complexity is equivalent to the spectral one.
>  This order implies the reversed one induced by the operator entropy.
> 
> 
> 


