The matrix corresponds to the 2-dimensional hypercube using a normal binary ordering (indexing included only to show nodes, this is a matrix)
We can use this matrix inductively. Adding one extra symbol, hence a matrix will look like
will only have entries which differ by one from the entries in . Clearly, this can only be the identity matrix! We note that we have identity matrices in these positions also in .
More general, for a -dimensional hypercube, we have that
Why is this the case? We can take two hypercubes of two dimensions and put together to obtain a three dimensional hypercube (well, a cube). Each vertex in the first hypercube is connected with another vertex (in the corresponding position) in the second hypercube. Of course this is the case for any dimension.
The recursive nature and commutativity of the submatrices allows us to give a recursive formula for the characteristic polynomial.
We use a simple combinatorial argument. The -value can take on step up och one step down in each induction step which gives us that the eigenvalues for will be and their corresponding multiplicities .