Are matrices best understood as linear maps?

Any linear map between finite-dimensional vector spaces may be represented by a matrix, and conversely. Matrix-matrix multiplication corresponds to map composition, and matrix-vector multiplication corresponds to map application.

This provides a nice way of understanding matrices and the origin of the rules for their calculation. Having attained this perspective is a huge boon to me, because I've always resented that matrix math is basically just taught as a collection of arbitrary manipulations of symbols (multiply the entries! now add them! don't ask why!).

But is this understanding always meaningful?

For in general, just because you've found an interpretation for a mathematical concept doesn't mean it will always apply. For instance, the trig functions can be thought of as simply being the coordinates on a unit circle, but this fails to explain why they show up as solutions to differential equations having nothing to do with circles (or indeed geometry) - to explain this we require a more abstract understanding of the trig functions.

Thus, in all non-trivial uses of matrices in pure and applied mathematics, can we meaningfully say that the matrices involved represent, at least implicitly, linear maps? For instance, we can think of solving a system of equations as simply trying to find a vector which, when a given map is applied to it, yields a specific image.

By non-trivial, I mean that the particular use of matrices involves, at minimum, matrix multiplication and/or determinants or other elementary aspects of the calculus of matrices. For instance, you could call a spreadsheet a matrix, but unless you intend to do anything matrix-like with it apart from draw it as a grid, you may as well just call it a set of numbers.

Note: this question may be soft, but I feel it can be given a clean answer. Either you can come up with a situation where the linear-map interpretation doesn't apply, or you can't.

I think that when you see a matrix multiplication, more likely than not there will be a composition or application of a linear map going on. However I've seen very remarkable determinants being evaluated (in combinatorics notably) where it is really very hard to bring any linear operation into the picture. Sometimes arranging expressions into a matrix is just a convenient notational means to create a very complicated combination of those expressions simply by applying $\det$.

Here is an example. For a partition $\lambda=(\lambda_0,\lambda_1,\ldots,\lambda_k)$ (with therefore $\lambda_0\geq\lambda_1\geq\cdots\geq\lambda_k\geq0$) one can define the Schur polynomial $s_\lambda\in\mathbf Z[X_0,X_1,\ldots,X_k]$ by $$ s_\lambda = \frac{\begin{vmatrix} X_0^{\lambda_0+k}&X_0^{\lambda_1+k-1}&\cdots&X_0^{\lambda_{k-1}+1}&X_0^{\lambda_k}\\ X_1^{\lambda_0+k}&X_1^{\lambda_1+k-1}&\cdots&X_1^{\lambda_{k-1}+1}&X_1^{\lambda_k}\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ X_{k-1}^{\lambda_0+k}k&X_{k-1}^{\lambda_1+k-1}&\cdots&X_{k-1}^{\lambda_{k-1}+1}&X_{k-1}^{\lambda_k}\\ X_k^{\lambda_0+k}&X_k^{\lambda_1+k-1}&\cdots&X_k^{\lambda_{k-1}+1}&X_k^{\lambda_k}\\ \end{vmatrix}} {\begin{vmatrix} X_0^k&X_0^{k-1}&\cdots&X_0^1&1\\ X_1^k&X_1^{k-1}&\cdots&X_1^1&1\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ X_{k-1}^k&X_{k-1}^{k-1}&\cdots&X_{k-1}^1&1\\ X_k^k&X_k^{k-1}&\cdots&X_k^1&1\\ \end{vmatrix}} = \frac{\det\bigl((X_i^{\lambda_j+k-j})_{i,j=0}^k\bigr)}{\prod_{0\leq i<j\leq k}(X_i-X_j)}. $$ Here I would have a hard time bringing a linear map into the picture in any useful manner.

Note that a Matrix is not a linear function, it is just a matrix. With a basis given we can interpret it as a linear function. For example there are matrixes that represents graph (like the vertex or so called adjacency matrix which don't represent linear maps).

You have set of vertices $\{P_i\}_{1\leq i \leq n}$ and the matrix $M$ is a $n \times n$ with $$m_{ij} = \left\{\begin{array}{rl} 1 & P_i \to P_j\\ 0& \text{else} \\ \end{array}\right.$$

The power of the linear map point of view is that it doesn't depend on the choice of a basis. On the other hand, for problems which inherently involve a fixed basis, typically matrices are better suited.

One example is the Gauss algorithm. I don't know a single linear algebra book presenting it for linear maps. The matrices are more intuitive here.

The reason is the following: You cannot express the Gauss algorithm it in terms of linear maps alone, you additionally need some fixed basis of the vector space. (the elementary transformations, the reduced row echelon form etc. depend on a basis). Using matrices, that is not necessary, since there is already a distinguished basis of the vector space (the canonical one).