n -立方体

本节提供了斯坦利书第二章的一些例子 [Stanley2013], 其中涉及 n -立方体、Radon变换和组合公式 n -立方体。

的顶点 n -立方体可以用向量来描述 mathbb{{Z}}_2^n . 首先我们定义两个向量的加法 u,v in mathbb{{Z}}_2^n 通过以下距离：

sage: def dist(u,v):
....:     h = [(u[i]+v[i])%2 for i in range(len(u))]
....:     return sum(h)

距离函数测量两个向量在多少槽中 mathbb{{Z}}_2^n 不同之处：

sage: u=(1,0,1,1,1,0)
sage: v=(0,0,1,1,0,0)
sage: dist(u,v)
2

现在我们要定义 n -立方体作为顶点在 mathbb{{Z}}_2^n 顶点之间的边 u 和顶点 v 如果它们在一个槽中不同，即距离函数为1:：

sage: def cube(n):
....:     G = Graph(2**n)
....:     vertices = Tuples([0,1],n)
....:     for i in range(2**n):
....:         for j in range(2**n):
....:             if dist(vertices[i],vertices[j]) == 1:
....:                 G.add_edge(i,j)
....:     return G

我们可以画出 3 和 4 -立方体：

sage: cube(3).plot()
Graphics object consisting of 21 graphics primitives

sage: cube(4).plot()
Graphics object consisting of 49 graphics primitives

接下来，我们可以在Stanley的书中实验和检查推论2.4，该书指出 n -多维数据集有 n 选择 i 特征值等于 n-2i ：：

sage: G = cube(2)
sage: G.adjacency_matrix().eigenvalues()
[2, -2, 0, 0]

sage: G = cube(3)
sage: G.adjacency_matrix().eigenvalues()
[3, -3, 1, 1, 1, -1, -1, -1]

sage: G = cube(4)
sage: G.adjacency_matrix().eigenvalues()
[4, -4, 2, 2, 2, 2, -2, -2, -2, -2, 0, 0, 0, 0, 0, 0]

现在很容易稍微改变这个问题，并通过连接顶点来更改边集 u 和 v 如果他们的距离是2（见第2章的问题4）：

sage: def cube_2(n):
....:     G = Graph(2**n)
....:     vertices = Tuples([0,1],n)
....:     for i in range(2**n):
....:         for j in range(2**n):
....:             if dist(vertices[i],vertices[j]) == 2:
....:                 G.add_edge(i,j)
....:     return G

sage: G = cube_2(2)
sage: G.adjacency_matrix().eigenvalues()
[1, 1, -1, -1]

sage: G = cube_2(4)
sage: G.adjacency_matrix().eigenvalues()
[6, 6, -2, -2, -2, -2, -2, -2, 0, 0, 0, 0, 0, 0, 0, 0]

请注意，图实际上是断开的。你明白为什么吗？

sage: cube_2(4).plot()
Graphics object consisting of 65 graphics primitives