The existence of an algebra homomorphism between $\mathcal{M}_n({\mathbb{K}})$ and $\mathcal{M}_s(\mathbb{K})$ implies $n | s$ Let $n,s \geq 1$ be integers and $\mathbb{K}$ a field.
We assume there exist $\Phi : \mathcal{M}_n(\mathbb{K}) \rightarrow \mathcal{M}_s(\mathbb{K})$ an unital algebra homomorphism ($\Phi(I_n)=I_s$). See here for the definition.
We must show that necessarily $n | s$ and there exists $P \in \textrm{GL}_s(\mathbb{K})$ such that for all $A \in \mathcal{M}_n(\mathbb{K})$ :
$$
P \cdot \Phi(A) \cdot P^{-1} = \begin{pmatrix}
A & & (0)\\
 & \ddots &\\
(0) & & A \\
\end{pmatrix}
$$
I have tried, but I cannot find a way to exploit $\Phi$ to show this. I am looking for a solution of this that uses only "basic" theorems of linear algebra (Bachelor's level). Any help is welcome.
 A: Any $M_s(K)$-module becomes an $M_n(K)$-module via pullback under the the
map $\Phi$. So, consider $K^s$ as the tautological $M_s(K)$-module. This is
also a $M_n(K)$-module. But $M_n(K)$ is semisimple, 
and up to isomorphism its only simple module is $K^n$. As $\Phi$ is a $K$-algebra
map, then $K^n$ also has dimension $n$ as a $K$-vector space, even when
viewed as a $K^n$-modules. It must be a direct sum of $r$ simple $M_n(K)$-modules.
Via a dimension count $rn=s$, so $n\mid s$.
The existence of $P$ is essentially the Noether-Skolem theorem. We can split up $K^s=N_1\oplus\cdots\oplus N_r$ where the $N_j$ are simple $M_n(K)$-modules.
So we can choose a basis of $K^s$ so that
$$\Phi=\pmatrix{\Phi_1&0&\cdots&0\\0&\Phi_2&\cdots&0\\\vdots&\vdots
&\ddots&\vdots\\0&0&\cdots&\Phi_r}$$
with respect to this basis. Each $\Phi_i$ is a $K$-automorphism of $M_n(K)$
which is an inner automorphism due to Noether-Skolem.
A: Not sure some "bachelor level" solution is at hand. What is stated in the text ( not in the title) is nothing less than Noether-Skolem in the particular case $n=s$.  
Just for fun,  let's show that $n\mid s$  without modules, but with determinants. Consider a morphism $\Phi$ from $M_n(\mathbb{K})$ to $M_s(\mathbb{K})$. Denote by $\Delta$ the composition $\det \circ \Phi$. It takes conjugate matrices in $M_n(\mathbb{K})$ to the same element in $\mathbb{K}$. Let $\alpha \in \mathbb{K}$, and $D_{\alpha}$ a diagonal matrix with one element on the diagonal $\alpha$ and the rest $1$. Note they are all conjugate ($n$ of them). Now, $\Delta(D_{\alpha})$ is a polynomial expression in $\alpha$, denote it by $P_(\alpha)$, with coefficients in $\mathbb{K}$. Moreover, since the $n$ matrices of type $D_{\alpha}$ have product $\alpha \cdot I_n$, we have $P(\alpha)^n = \det (\alpha \cdot I_s) = \alpha^s$. 
Assume for a moment that $\mathbb{K}$ is infinite. Since a polynomial function on $\mathbb{K}$ comes from a unique polynomial, by considering degrees in the above equality we get $n\mid s$.
We can get away with the hypothesis $\mathbb{K}$ infinite by realizing that a morphism from $M_n(\mathbb{K})$ to $M_s(\mathbb{K})$ gives morphisms from $M_n(\mathbb{ K'})$ to $M_s(\mathbb{K'})$ for any field extension $\mathbb{K'}$ of $\mathbb{K}$.
A: We do not need the full strength of Noether-Skolem here; as per Lord Shark's solution, we only need to show that any $k$-automorphism $\phi: M_n (k) \to M_n (k)$ is of the form $\phi(X) = TXT^{-1}$ for some $T \in M_n (k)$.
This follows from the fact that $M_n (k)$ is a semisimple algebra whose only simple module, up to isomorphism, is $k^n$ with the standard action of $M_n (k)$. Suppose this fact. We may construct a "twisted" $M_n (k)$ action on $k^n$ by declaring $X \cdot v := \phi(X)(v)$ for $X\in M_n (k)$ and $v\in k^n$. This twisted representation of $M_n (k)$ must be isomorphic to the standard representation of $M_n (k)$, hence there exists a module isomorphism $$T: k^n (\text{standard}) \to k^n (\text{twisted})$$ In particular, for any $X\in M_n (k)$ and $v \in k^n$, we have $$\phi(X)(Tv) = x \cdot (Tv) = T(Xv) \implies (T^{-1} \phi(X) T)v = Xv$$ and thus $T^{-1} \phi(X) T = X$ for all $X\in M_n (k)$, i.e. $\phi(X) = TXT^{-1}$.
A: An approach with more basic tools only. Towards the end it is a bit sketchy. It is kind of a notational nightmare! I hope I managed to communicate the key ideas though. The desired matrix $P$ will be built in several stages.

Let $E_{ij}\in M_n(\Bbb{K})$ be the matrix with entry $1$ at position $(i,j)$ and zeros elsewhere. Let $F_{ij}=\Phi(E_{ij})\in M_s(\Bbb{K})$.


*

*The matrices $E_{ii},i=1,2,\ldots,n,$ satisfy the relations $$E_{ii}E_{jj}=\delta_{ij}E_{ii}.\tag{1}$$ Therefore the same relation holds for their images $F_{ii}$.

*If a matrix $A\in M_s(\Bbb{K})$ satisfies the relation $A^2=A$, then $A$ is diagonalizable. This is because every vector $x\in\Bbb{K}^s$ can be written as a sum of eigenvectors of $A$:
$$x=(x-Ax)+Ax,\tag{2}$$ with $x-Ax$ belonging to eigenvalue $0$ and $Ax$ belonging to eigenvalue $1$, both owing to $A^2=A$. The conclusion is that all the matrices $F_{ii}$ are diagonalizable and have eigenvalues zero and one only.

*Another consequence of $(1)$ is that the matrices $F_{ii}$ all commute, because $F_{ii}F_{jj}=0$ whenever $i\neq j$.

*A commuting set of diagonalizable matrices is simultaneously diagonalizable, i.e. there exists a matrix $P_1\in GL_s(\Bbb{K})$ such that all the matrices $P_1F_{ii}P_1^{-1},i=1,2,\ldots,n$, are diagonal. Ask, if you have not seen this result – comes in handy at many places.

*At this point we can forget about $P_1$ and without loss of generality simply assume that the $F_{ii}$s are diagonal with entries from $\{0,1\}$.

*Let $1\le i\neq j\le n$ be a pair of indices, and $S$ be the permutation matrix gotten from $I_n$ by interchanging rows $i$ and $j$. We have $SE_{ii}S^{-1}=E_{jj}$, so it follows that $F_{ii}$ and $F_{jj}$ are also conjugates (by $\Phi(S)$). If we denote by $m_i$ the multiplicity of $1$ as an eigenvalue of $F_{ii}$, it follows that $m_i=m_j=m$ for all $i,j$. In other words, each of the matrices $F_{ii}$ has $m$ ones on the diagonal, and the rest of their entries are all zeros. As $F_{ii}F_{jj}=0$ whenever $i\neq j$, their respective $1$ entries won't overlap.

*We have $I_n=\sum_{i=1}^nE_{ii}$, so it follows that
$$I_s=\Phi(I_n)=\sum_{i=1}^nF_{ii}.\tag{3}$$

*From $(3)$ it follows that $s$, the trace of $I_s$, is equal to the sum of the traces of $F_{ii}$s, in other words $s=nm$, proving the first claim that $n\mid s$.

*From the above observations it follows that there is a permutation matrix $P_2\in M_s(\Bbb{K})$ such that the non-zero entries of $P_2F_{ii}P_2^{-1}$, $i=1,2,\ldots,n$, are in positions $i,i+n,i+2n,\ldots,i+(m-1)n$. Again without loss of generality we absorb $P_2$ into $\Phi$ and assume that this is the case. At this point we know that main claim holds for the matrices $A=E_{ii}$, $i=1,2,\ldots,n$, and hence it holds whenever $A$ is diagonal. 


Then we need to take control of the images $F_{ij}=\Phi(E_{ij}), i\neq j$.
For $i=1,2,\ldots,n$, let's denote by $V_i$ the subspace of $\Bbb{K}^s$ spanned by
the standard basis vectors $e_t$ with $t\equiv i\pmod n$, $t=1,2,\ldots,s$. With the steps above in place we know that $F_{ii}$ is the identity transformation on the subspace $V_i$ but vanishes elsewhere.


*

*From the relations (for all $i,j,k, i\neq j$)
$$E_{kk}E_{ij}=\delta_{ik}E_{ij}, E_{ij}E_{kk}=\delta_{jk}E_{ij}$$
we arrive at the relations
$$F_{kk}F_{ij}=\delta_{ik}F_{ij}, F_{ij}F_{kk}=\delta_{jk}F_{ij}.\tag{4}$$

*From $(4)$ it follows that the non-zero entries of $F_{ij}$ can only occur on rows $\equiv i\pmod n$ and columns $\equiv j\pmod n$, for the other entries would survive pre/post multiplication by a suitable $F_{kk}$. 

*In other words, as a linear transformation $F_{ij}$ maps the subspace $V_j$ into the subspace $V_i$, and $F_{ij}(V_k)=0$ for all $k\neq i$. We denote this linear transformation $\phi_{ij}:V_i\to V_j$.

*The remaining key relations are
$$F_{ij}F_{k\ell}=\delta_{jk}F_{i\ell}\tag{5}$$ that follow from the corresponding relations satisfied by the $E_{ij}$s.

*For a fixed pair of indices $i\neq j$ we have $F_{ij}F_{ji}=F_{ii}$ and $F_{ji}F_{ij}=F_{jj}$. It follows that $\phi_{ij}$ and $\phi_{ji}$ are inverses of each other.

*Let us a fix a basis $\mathcal{B}_1$ for the subspace $V_1$. For all $j=2,3,\ldots,n$, let then $\mathcal{B}_j=\phi_{1j}(\mathcal{B}_1)$ be a corresponding basis of $V_j$.

*In the final step we vrite all the linear transformations in $\mathrm{Im}(\Phi)$ w.r.t. the basis $\bigcup_{j=1}^n\mathcal{B}_j$. The relations $(5)$ are the compatibility relations guaranteeing that the matrices representing $F_{ij}$ must have the desired block form. By linearity, the same holds for all the matrices $A$.

