Here is a ridiculous solution using a $1 \times 1$ matrix! First, encode an $n \times n$ adjacency matrix $A$ by $a \lt \binom{n-1}2$ where $a$ is binary integer obtained by listing the above diagonal entries row by row. Use with all $n!$ adjacency matrices getting an multi-set of $n!$ integers which we can give the natural order. Finally, encode the graph as the $1\times 1$ matrix $[2^{a_1}3^{a_2}\cdots]$ using the first $n!$ primes.
This could be greatly enhanced, for example use instead the base $3$ integer with $n!-1$ $2$’s separating $a_12a_22a_32\cdots.$
‘