Here is a ridiculous solution using a $1 \times 1$ matrix! First, encode an $n \times n$ adjacency matrix $A$ by $\alpha=2^a \lt 2^{\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 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^{\alpha_1}3^{\alpha_2}\cdots]$ using the first $n!$ primes.
‘