generating distanced matrix for an n-dimensional hypercube

Question

is there any algorithm or method of generating the adjacency matrix for a hypercube for any dimension? say your input is 5 it would create a 5-dimensional hypercube

all i can find are sources from wiki

and wolfram

Answer 1

I know that this is a bit late, but the solution is distinct from the others and based on recursion, so hopefully someone will find it useful.

First lets build some intuition about how to build an N-cube from an (N-1) cube! When you think of a 1-cube, it's just a line segment. To get a 2-cube(square), we make a copy of the line segment, translate it, and add edges along the path of translation. Similarly, to get a 3-cube, we take that square, make a copy of it, translate it, and add the translation edges. If you have a hard time visualizing that, contemplate the image below:

If only there was mathematical machinery that does this! We're in luck because there is: the Kronecker product. In essence it gives us a way to copy adjacency matrices, and then it's just a matter of glueing the results together. Glueing is accomplished by adding the dashed lines in the above figures as additional edges in the adjacency matrix of the two copies of the lower dimensional cubes. In picture form (because this heathen site doesn't support LaTeX): And that's that! The adjacency matrix for a hypercube of arbitrary dimension is the sum of these two pieces. One last caveat: these matrices grow exponentially and are mostly filled with zeros (each node only connects to N of the 2^N other nodes), so sparse matrices are a must. Here's a quick MATLAB implementation. Enjoy!

function A = hypercube(N)
  if N==1
    A = sparse([0 1;1 0]);
  else
    A = kron(sparse(eye(2)),hypercube(N-1)) + ...
         kron(hypercube(1),diag(sparse(ones(1,2^(N-1)))));
  end
end