re **Puzzle 181**:

> Suppose that \\(\Phi : X \nrightarrow Y, \Psi : Y \nrightarrow Z\\) are feasibility relations between preorders. Prove that

>

> \[ (\Psi\Phi)(x,z) = \bigvee_{y \in Y} \Phi(x,y) \wedge \Psi(y,z) \]

>

> where \\(\wedge\\) is the meet in the poset \\(\textbf{Bool}\\), and \\(\bigvee\\) is the join.

>

> How is this formula related to matrix multiplication?

If \\((\Psi\Phi)(x,z) = \text{true}\\), then by definition we must have \\(\Phi(x,y) \wedge \Psi(y,z) = \text{true}\\) for at least one \\(y\in Y\\), so the join of all \\(\Phi(x,y) \wedge \Psi(y,z)\\) must be \\(\text{true}\\).

If \\((\Psi\Phi)(x,z) = \text{false}\\), then we must have \\(\Phi(x,y) \wedge \Psi(y,z) = \text{false}\\) for all \\(y\in Y\\), so the join of all \\(\Phi(x,y) \wedge \Psi(y,z)\\) will be \\(\text{false}\\).

We can think of this join-of-meets as a sum-of-products, and specifically as the product of the "row vector" \\((\Psi(y_0,z)\ \Psi(y_1,z)\ \Psi(y_2,z)...)\\) with the "column vector" \\((\Phi(x,y_0)\ \Phi(x,y_1)\ \Phi(x,y_2)...)^\textbf{T}\\). This suggests the following construction:

Given any feasibility relation \\(\Phi : X \nrightarrow Y\\) we construct a matrix \\(\text{M}(\Phi)\\) with \\(|X|\\) columns, \\(|Y|\\) rows, and the boolean \\(\Phi(x, y)\\) at position \\((y, x)\\).

Then what we've just proved amounts to \\(\text{M}(\Psi\Phi) = \text{M}(\Psi)\text{M}(\Phi)\\).

> Suppose that \\(\Phi : X \nrightarrow Y, \Psi : Y \nrightarrow Z\\) are feasibility relations between preorders. Prove that

>

> \[ (\Psi\Phi)(x,z) = \bigvee_{y \in Y} \Phi(x,y) \wedge \Psi(y,z) \]

>

> where \\(\wedge\\) is the meet in the poset \\(\textbf{Bool}\\), and \\(\bigvee\\) is the join.

>

> How is this formula related to matrix multiplication?

If \\((\Psi\Phi)(x,z) = \text{true}\\), then by definition we must have \\(\Phi(x,y) \wedge \Psi(y,z) = \text{true}\\) for at least one \\(y\in Y\\), so the join of all \\(\Phi(x,y) \wedge \Psi(y,z)\\) must be \\(\text{true}\\).

If \\((\Psi\Phi)(x,z) = \text{false}\\), then we must have \\(\Phi(x,y) \wedge \Psi(y,z) = \text{false}\\) for all \\(y\in Y\\), so the join of all \\(\Phi(x,y) \wedge \Psi(y,z)\\) will be \\(\text{false}\\).

We can think of this join-of-meets as a sum-of-products, and specifically as the product of the "row vector" \\((\Psi(y_0,z)\ \Psi(y_1,z)\ \Psi(y_2,z)...)\\) with the "column vector" \\((\Phi(x,y_0)\ \Phi(x,y_1)\ \Phi(x,y_2)...)^\textbf{T}\\). This suggests the following construction:

Given any feasibility relation \\(\Phi : X \nrightarrow Y\\) we construct a matrix \\(\text{M}(\Phi)\\) with \\(|X|\\) columns, \\(|Y|\\) rows, and the boolean \\(\Phi(x, y)\\) at position \\((y, x)\\).

Then what we've just proved amounts to \\(\text{M}(\Psi\Phi) = \text{M}(\Psi)\text{M}(\Phi)\\).