# Sumcheck Protocol: How to represent a matrix as an MLE which takes row & column numbers as parameters?

This is from Justin Thaler's book - Proofs, Arguments & Zero Knowledge

Page 43

For it to make sense to talk about multilinear extensions, we need to view the adjacency matrix $$A$$ not as a matrix, but rather as a function $$f_A$$ mapping $$\lbrace0,1\rbrace^ {log n} \times \lbrace0,1\rbrace^ {log n}$$ to $$\lbrace0,1\rbrace$$. The natural way to do this is to define $$f_A(x,y)$$ so that it interprets $$x$$ and $$y$$ as the binary representations of some integers $$i$$ and $$j$$ between $$1$$ and $$n$$, and outputs $$A_{i, j}$$. See Figure $$4.5$$ for an example.

This is figure 4.5 (I have shaded in yellow the element which I am going use below as an example).

The 4 parameters of function $$f_A$$ seem to be the bit representation of the element number of the matrix - i.e if I consider the matrix elements having numbers $$0$$ to $$15$$ (Considering element numbers of first row as $$0, 1, 2$$ & $$3$$ & so on)

For e.g. if I consider the element $$6$$ in row number $$4$$ & column number $$2$$- it's the $$13$$th element of the Matrix. The bit pattern of $$13$$ is $$1101$$.

So $$f_A$$ takes 4 parameters same as the bit pattern - i.e. $$f_A(1,1,0,1) = 6$$

I hope my understanding above is correct.

However, right after, on Page 44, he says counts triangles using the following equation

$$\Delta = \frac {1}{6} \sum_{{x,y,z \in \lbrace 0, 1 \rbrace}^{log\space n}} f_A(x,y)\cdot f_A(y,z) \cdot fA(x,z)$$

I assume above that the parameters to $$f_A$$ are row & column numbers.

In figure $$4.5$$, the parameters of $$f_A$$ is the bit pattern of the element number of the matrix. However, above it changes to row & column numbers. How does this match with figure $$4.5$$?

In the particular case of a $$4 \times 4$$ matrix the element number bit pattern is the same as bit pattern of row number joined with bit pattern of column number. But this isn't true for others - i.e. not true even for $$5\times 5$$?

In figure 4.5, the parameters of $$f_A$$ is the bit pattern of the element number of the matrix. However, above it changes to row & column numbers. How does this match with figure 4.5?
The inputs to $$f_A$$ are always a pair consisting of a row and column. If the book wanted to be extremely precise, they would have used the following notation, for example $$f_A((1,1),(0,1)) = 6.$$ But that can hurt readability.
True. The example simplifies to make it work nicely. But for the general case, I believe the "fix" is to arbitrarily define the values of $$f_A$$ at inputs that aren't valid indices. Then, one can use something akin to a selector polynomial in the specific application (that evaluates to zero, for example, in a counting application, etc..).
• fA((1,1),(0,1))=6. with such a definition, how exactly would you use Lemma 3.6 (Page 29) to interpolate & find the polynomial which would represent the matrix? Nov 13 at 14:08
• There's a 1-1 mapping from $((w,x),(y,z))$ to $(w, x ,y ,z)$. So you can define an intermediary function that "flattens" the tuple before doing the interpolation. At this point, it's mainly a question of presentation. Nov 13 at 14:13
• Thank you. So the sumcheck also instead of $\sum_{{x,y,z \in \lbrace 0, 1 \rbrace}^{log\space n}} f_A(x,y)\cdot f_A(y,z) \cdot fA(x,z)$ would also become something like $\sum_{x_1 \in \lbrace 0, 1 \rbrace} ... \sum_{y_1 \in \lbrace 0, 1 \rbrace} ... \sum_{z_1 \in \lbrace 0, 1 \rbrace}... f_A(x_1, x_2, ..., y_1, y_2, ..., z_1, z_2, ...)$ Nov 14 at 10:40
• You can certainly define things such that the expression you give works. But I suppose the "ultimate" implementation will still be something like $f_A(x_1,\cdots, y_1, \cdots) f_A(y_1,\cdots, z_1, \cdots) f_A(z_1,\cdots, x_1, \cdots)$. The reason being that the running time for the MLE evaluation is basically exponential in the number of variables in $f_A$. But surely, the long expression you can be used either directly or as "syntactic sugar" for the more efficient implementation. Nov 14 at 13:34