I was talking about matrix/matrix composition (rather than multiplication) at first. Then I talked about matrix application.

A matrix is a function. Not all functions can be represented by matrices (although all smooth functions can be represented by a Taylor series that sums over matrices (and "the sum C=A+B" really means "the function C such that Cx = Ax+Bx for all x in the range of both A and B"))

I rather dislike this way of saying things. A matrix is a matrix, its a table of numbers, and one can usefully define operations like addition and multiplication on them.

A linear map is a linear map, it maps between vector spaces and it obeys some nice axioms. You can define addition and composition as operations on them.

It is a quite interesting and non-trivial theorem that if you fix a particular choice of basis then you get "for free" a bijection between linear maps and matrices. The bijection between matrices and linear maps is completely dependent on the basis you choose, however, and there certainly isn't a canonical way to choose the basis.

Often it is natural to change basis to make it easier solve some particular problem, and then the matrix that represents a particular linear map will change, but the properties of the linear map won't change (for example its rank, kernel, eigenvectors/values etc).