>I know that matrix multiplication was introduced by Cayley (correct me if I am wrong)
Gauss in *Disquisitiones Arithmeticae* (1801) has something called not matrix multiplication but ***combination of substitutions*** — e.g. he writes near the end of [§294](//archive.org/details/werkecarlf01gausrich/page/n361):
>$(S)=\left\{\!\!\begin{smallmatrix}
\phantom{-}7245,&\phantom{0}5,&\phantom{-}22\\
-2415,&\phantom{0}2,&-28\\
19320,&25,&\phantom{0}-7
\end{smallmatrix}\!\right\}$ combined with
$(S')=\left\{\!\!\begin{smallmatrix}
\phantom{-000}3,&\phantom{-000}5,&\phantom{-00}1\\
-2440,&-4066,&-813\\
\phantom{0}-433,&\phantom{0}-722,&-144
\end{smallmatrix}\!\right\}$ produces
$\left\{\!\!\begin{smallmatrix}
\phantom{-}9,&11,&12\\
-1,&\phantom{0}9,&-9\\
-9,&\phantom{0}4,&\phantom{0}3\end{smallmatrix}\!\right\}$.
His definition is in [§270](//archive.org/details/werkecarlf01gausrich/page/n313):
