Here is a ridiculous solution using a $1 \times 1$ matrix! First, encode an $n \times n$ adjacency matrix $A$ by $a \lt 2^{\binom{n-1}2}$ where $a$ is the 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.$

‘Actually, one could just use the lexicographically least $n \times n$ adjacency matrix. This would have the vertices in decreasing order of degree. That alone is no help for regular graphs, but for others it might cut the number of cases.