Correspondence between addressings of a graph and quadratic forms

50 Views Asked by At

In "A course in combinatorics" by Lint and Wilson, 2nd edition, the example on page 78, we have a simple graph (5 vertices)

enter image description here

with the possible addressing

enter image description here

To the first column, we associate the product $(x_1 + x_2)(x_4 + x_5)$. Here $x_i$ is the first, respectively second factor, if the address of $x_i$ has a $1$, respectively a $0$, in the first column. Doing the same for colums, we obtain the quadratic form $$ \sum d_{ij} x_i x_j $$ where $d_{ij}$ is the distance between $x_i$ and $x_j$ in $G$. In matrix notation, $\frac{1}{2}{\bf x}^TA{\bf x}$.

What are the entries of $\bf x$ and $A$, please? I am a beginner in combinatorics.

1

There are 1 best solutions below

2
On BEST ANSWER

Not a very clear question, but I'll try to answer it. The entries of the matrix $A$ are $d_{ij}$, where $d_{ij}$ is the distance between two vertices $x_i$ and $x_j$ in our graph. For the graph in your figure we get $$ A= \begin{pmatrix} 0 & 1 & 2 & 2 & 3\\ 1 & 0 & 1 & 1 & 2\\ 2 & 1 & 0 & 1 & 1\\ 2 & 1 & 1 & 0 & 1\\ 3 & 2 & 1 & 1 & 0 \end{pmatrix}. $$ Here $\bf x$ is the column of independent variables $x_i$. Let us denote our quadratic form $f$, that is, $f=\frac{1}{2}{\bf x}^TA{\bf x}$. We have \begin{align*} f&=\frac{1}{2}{\bf x}^TA{\bf x}\\ &=(x_1+x_2)(x_4+x_5)\\ &+x_1(x_2+x_3+x_4+x_5)\\ &+(x_1+x_4)(x_3+x_5)\\ &+x_2(x_3+x_5)\\ &+x_3x_5 \end{align*} The line with the number $i$ of the last formula corresponds to the $i$th column of your coding table. I strongly recommend that you check this equality. I think you will see that this kind of equality is always true, not only for this particular graph.

Addition.
Again ${\bf x}=(x_1,x_2,\ldots,x_n)^T$, where $x_i$ are independent variables. These variables in our case can take arbitrary real values. Further, $f$ is not a scalar, $f$ is a quadratic form, or a homogeneous polynomial of degree $2$, or if you like, a function in $n$ variables $x_i$.