Is a linear map (transformation) always a matrix multiplication

The answer is yes. If you have a linear map $\phi: V \to W$, between finite dimensional vector spaces of dimension $n$ resp $k$, then this gives rise to a matrix in the following way:

Choose a basis $\{x_i\}$ of $V$ and $\{y_1\}$ of $W$.
Then the matrix corresponds to how $\phi$ acts on the $x_i$ in terms of $y_i$.

As $\phi(x_i)\in W$, we can find coefficients $m^j_i$ such that $$\phi(x_i)=\sum_{j=1}^k m^j_i y_j.$$The coefficients $m^j_i$ correspond to the entries of the matrix $M$ representing $\phi$.

In particular, if $\{y_i\}$ are an orthogonal basis, we can calculate $m^j_i$ by $$m^j_i=<y_j,\phi(x_i)>.$$

Further, for an arbitrary vector $ v = \sum_{i=1}^n a^i x_i \in V$ (with some coefficients $a_i$), we have that $$\phi(v)=\phi( \sum_{i=1}^n a^i x_i) = \sum_{i=1}^n a^i \phi(x_i) = \sum_{i=1}^n a^i m^j_i y_i.$$ From the formula for multiplicating a vector with a matrix, we see that in this basis, the components of $\phi(v)$ correspond to the entries of $Mv$

---

Edit: A short remark as a reply to a comment:
$M$ is not $\phi$. $\phi$ is a linear map between $V$ and $W$, whereas $M$ is a matrix and thus induces a linear map between $\mathbb R^n$ and $\mathbb R^k$ by $x \mapsto Mx$. $M$ only represents $\phi$, that is the following diagram commutes:

$$ \newcommand{\ra}[1]{\!\!\!\!\!\!\!\!\!\!\!\!\xrightarrow{\quad#1\quad}\!\!\!\!\!\!\!\!} \newcommand{\da}[1]{\left\downarrow{\scriptstyle#1}\vphantom{\displaystyle\int_0^1}\right.} % \begin{array}{llllllllllll} V & \ra{\phi} & W \\ \da{} && \da {} \\ \mathbb R^n & \ra{M \cdot} & \mathbb{R}^k \\ \end{array} ,$$ where the vertical maps are the isomorphisms given by choosing a basis.

Yes it's alway possible use matrices for linear maps!

https://en.wikipedia.org/wiki/Linear_map