How do you marginalize in graphical model elimination? I'm reading Michael I. Jordan's book on probabilistic graphical models, and I don't understand the elimination algorithm presented in chapter 3. To narrow the question down, consider page 6. In equation (3.10), we see that $$m_5(x_2,x_3) = \sum_{x_5}p(x_5|x_3)p(\bar{x}_6|x_2,x_5)$$ where the $x_i$ are random variables and $\bar{x}_i$ indicates a fixed/realized value of $x_i$. Given that all $x_i$ are discrete random variables (as is the case in chapter 3), both $p(x_5|x_3)$ and $p(\bar{x}_6|x_2,x_5)$ are represented by two-dimensional matrices. And since $m_5$ is a function of as-yet unrealized variables $x_2$ and $x_3$, it is also a two-dimensional matrix. How then do we perform the multiplication and the summation above?

I'm realizing now that it's just regular matrix multiplication.

For the case above, let $p(x_5|x_3)$ and $p(\bar{x_6}|x_2,x_5)$ be represented by $r\\!\times\\!s$ and $s\\!\times\\! t$ matrices, respectively, where $x_5$ can take on $s$ different values. Then, for each element $m_{ij}$ of $m_5$, we have that

$$m_{ij}=\sum_{k=1}^s p_{ik}(x_5|x_3)p_{kj}(\bar{x_6}|x_2,x_5)$$

where $1\leq i \leq r$ and $1 \leq j \leq t$.

This is matrix multiplication. Also, intuitively, the dimensions will always work out, since each factor in the product will always be a function of the variable we're summing over.

I think the notation is what was tripping me up. I usually don't see matrix multiplication written explicitly as a sum of products.