Return to Answer

The key here is the bilinearity of $p\boxplus q$, in $p$ and $q$ (according to formula (24.2) in the lecture notes at http://www.cs.yale.edu/homes/spielman/561/lect24-15.pdf you referred to).

Suppose $M$ has all row sums equal $1$. Then so do $P_2MP_2^T,\dots,P_dMP_d^T$, and hence $N_Q:=P_2MP_2^T+\dots+P_dMP_d^T$ has all row sums equal $d-1$, where $Q:=(P_2,\dots,P_d)$. Therefore, the formula \begin{equation} \chi_x(N_Q)=(x-(d-1))p_Q(x)\tag{0} \end{equation} defines a polynomial $p_Q(x)$. Using that identity -- $$\underset{P}E\, \chi_x(A + PBP^T) = (x-(a+b))[p_1(x) \boxplus p_2(x)]$$ -- and the mentioned bilinearity of $\boxplus$, we have \begin{align*} &\underset{P_1,P_2,\dots,P_d}E\chi_x(P_1MP_1^T+ P_2MP_2^T+\dots+P_dMP_d^T) \\ &=\underset{Q}E\underset{P_1}E\chi_x(M+ P_1N_QP_1^T) \\ &=\underset{Q}E(x-(1+d-1))(p(x) \boxplus p_Q(x))\\ &=(x-d)(p(x) \boxplus \underset{Q}E\,p_Q(x)). \tag{1} \end{align*} On the other hand, by induction and formula (0), \begin{equation*} (x-(d-1))p^{\boxplus(d-1)}(x)=\underset{Q}E\,\chi_x(N_Q) =(x-(d-1))\underset{Q}E\,p_Q(x), \end{equation*} so that $\underset{Q}E\,p_Q(x)=p^{\boxplus(d-1)}(x)$, the $(d-1)$-fold finite free convolution of $p$ with itself. Now the desired result follows by (1).

The key here is the bilinearity of $p\boxplus q$, in $p$ and $q$ (according to formula (24.2) in the lecture notes at http://www.cs.yale.edu/homes/spielman/561/lect24-15.pdf you referred to).

In accordance with the OP's answer to my comment, suppose $M$ has all row sums equal $1$. Then so do $P_2MP_2^T,\dots,P_dMP_d^T$, and hence $N_Q:=P_2MP_2^T+\dots+P_dMP_d^T$ has all row sums equal $d-1$, where $Q:=(P_2,\dots,P_d)$. Therefore, the formula \begin{equation} \chi_x(N_Q)=(x-(d-1))p_Q(x)\tag{0} \end{equation} defines a polynomial $p_Q(x)$. Using that identity -- $$\underset{P}E\, \chi_x(A + PBP^T) = (x-(a+b))[p_1(x) \boxplus p_2(x)]$$ -- and the mentioned bilinearity of $\boxplus$, we have \begin{align*} &\underset{P_1,P_2,\dots,P_d}E\chi_x(P_1MP_1^T+ P_2MP_2^T+\dots+P_dMP_d^T) \\ &=\underset{Q}E\underset{P_1}E\chi_x(M+ P_1N_QP_1^T) \\ &=\underset{Q}E(x-(1+d-1))(p(x) \boxplus p_Q(x))\\ &=(x-d)(p(x) \boxplus \underset{Q}E\,p_Q(x)). \tag{1} \end{align*} On the other hand, by induction and formula (0), \begin{equation*} (x-(d-1))p^{\boxplus(d-1)}(x)=\underset{Q}E\,\chi_x(N_Q) =(x-(d-1))\underset{Q}E\,p_Q(x), \end{equation*} so that $\underset{Q}E\,p_Q(x)=p^{\boxplus(d-1)}(x)$, the $(d-1)$-fold finite free convolution of $p$ with itself. Now the desired result follows by (1).

The key here is the bilinearity of $p\boxplus q$, in $p$ and $q$ (according to formula (24.2) in the lecture notes at http://www.cs.yale.edu/homes/spielman/561/lect24-15.pdf you referred to).

Suppose $M$ has all row sums equal $1$. Then so do $P_2MP_2^T,\dots,P_dMP_d^T$, and hence $N_Q:=P_2MP_2^T+\dots+P_dMP_d^T$ has all row sums equal $d-1$, where $Q:=(P_2,\dots,P_d)$. So, using that identity, $$\underset{P}E\, \chi_x(A + PBP^T) = (x-(a+b))[p_1(x) \boxplus p_2(x)],$$ and the mentioned bilinearity of $\boxplus$, we have \begin{align*} &\underset{P_1,P_2,\dots,P_d}E\chi_x(P_1MP_1^T+ P_2MP_2^T+\dots+P_dMP_d^T) \\ &=\underset{Q}E\underset{P_1}E\chi_x(M+ P_1N_QP_1^T) \\ &=\underset{Q}E(x-(1+d-1))(p(x) \boxplus p_Q(x))\\ &=(x-d)(p(x) \boxplus \underset{Q}E\,p_Q(x)), \tag{1} \end{align*} where $p_Q(x)$ is the polynomial defined by the formula $\chi_x(N_Q)=(x-(d-1))p_Q(x)$; this definition is consistent, since all the row sums of $N_Q$ equal $d-1$. By induction and the definition of $p_Q(x)$, \begin{equation*} (x-(d-1))p^{\boxplus(d-1)}(x)=\underset{Q}E\,\chi_x(N_Q) =(x-(d-1))\underset{Q}E\,p_Q(x), \end{equation*} so that $\underset{Q}E\,p_Q(x)=p^{\boxplus(d-1)}(x)$, the $(d-1)$-fold finite free convolution of $p$ with itself. Now the desired result follows by (1).

The key here is the bilinearity of $p\boxplus q$, in $p$ and $q$ (according to formula (24.2) in the lecture notes at http://www.cs.yale.edu/homes/spielman/561/lect24-15.pdf you referred to).

Suppose $M$ has all row sums equal $1$. Then so do $P_2MP_2^T,\dots,P_dMP_d^T$, and hence $N_Q:=P_2MP_2^T+\dots+P_dMP_d^T$ has all row sums equal $d-1$, where $Q:=(P_2,\dots,P_d)$. Therefore, the formula \begin{equation} \chi_x(N_Q)=(x-(d-1))p_Q(x)\tag{0} \end{equation} defines a polynomial $p_Q(x)$. Using that identity -- $$\underset{P}E\, \chi_x(A + PBP^T) = (x-(a+b))[p_1(x) \boxplus p_2(x)]$$ -- and the mentioned bilinearity of $\boxplus$, we have \begin{align*} &\underset{P_1,P_2,\dots,P_d}E\chi_x(P_1MP_1^T+ P_2MP_2^T+\dots+P_dMP_d^T) \\ &=\underset{Q}E\underset{P_1}E\chi_x(M+ P_1N_QP_1^T) \\ &=\underset{Q}E(x-(1+d-1))(p(x) \boxplus p_Q(x))\\ &=(x-d)(p(x) \boxplus \underset{Q}E\,p_Q(x)). \tag{1} \end{align*} On the other hand, by induction and formula (0), \begin{equation*} (x-(d-1))p^{\boxplus(d-1)}(x)=\underset{Q}E\,\chi_x(N_Q) =(x-(d-1))\underset{Q}E\,p_Q(x), \end{equation*} so that $\underset{Q}E\,p_Q(x)=p^{\boxplus(d-1)}(x)$, the $(d-1)$-fold finite free convolution of $p$ with itself. Now the desired result follows by (1).

The key here is the bilinearity of $p\boxplus q$, in $p$ and $q$ (according to formula (24.2) in the lecture notes at http://www.cs.yale.edu/homes/spielman/561/lect24-15.pdf you referred to).

Suppose $M$ has all row sums equal $1$. Then so do $P_2MP_2^T,\dots,P_dMP_d^T$, and hence $N_Q:=P_2MP_2^T+\dots+P_dMP_d^T$ has all row sums equal $d-1$, where $Q:=(P_2,\dots,P_d)$. So, using that identity, $$\underset{P}E\, \chi_x(A + PBP^T) = (x-(a+b))[p_1(x) \boxplus p_2(x)],$$ and the mentioned bilinearity of $\boxplus$, we have \begin{align*} &\underset{P_1,P_2,\dots,P_d}E\chi_x(P_1MP_1^T+ P_2MP_2^T+\dots+P_dMP_d^T) \\ &=\underset{Q}E\underset{P_1}E\chi_x(M+ P_1N_QP_1^T) \\ &=\underset{Q}E(x-(1+d-1))(p(x) \boxplus p_Q(x))\\ &=(x-d)(p(x) \boxplus \underset{Q}E\,p_Q(x)), \tag{1} \end{align*} where $p_Q(x)$ is the polynomial defined by the formula $\chi_x(N_Q)=(x-(d-1))p_Q(x)$; this definition is consistent, since all the row sums of $N_Q$ equal $d-1$. By induction and the definition of $p_Q(x)$, \begin{equation*} (x-(d-1))p^{\boxplus(d-1)}(x)=\underset{Q}E\,\chi_x(N_Q) =(x-(d-1))\underset{Q}E\,p_Q(x), \end{equation*} so that $p_Q(x)=p^{\boxplus(d-1)}(x)$, the $(d-1)$-fold finite free convolution of $p$ with itself. Now the desired result follows by (1).

The key here is the bilinearity of $p\boxplus q$, in $p$ and $q$ (according to formula (24.2) in the lecture notes at http://www.cs.yale.edu/homes/spielman/561/lect24-15.pdf you referred to).

Suppose $M$ has all row sums equal $1$. Then so do $P_2MP_2^T,\dots,P_dMP_d^T$, and hence $N_Q:=P_2MP_2^T+\dots+P_dMP_d^T$ has all row sums equal $d-1$, where $Q:=(P_2,\dots,P_d)$. So, using that identity, $$\underset{P}E\, \chi_x(A + PBP^T) = (x-(a+b))[p_1(x) \boxplus p_2(x)],$$ and the mentioned bilinearity of $\boxplus$, we have \begin{align*} &\underset{P_1,P_2,\dots,P_d}E\chi_x(P_1MP_1^T+ P_2MP_2^T+\dots+P_dMP_d^T) \\ &=\underset{Q}E\underset{P_1}E\chi_x(M+ P_1N_QP_1^T) \\ &=\underset{Q}E(x-(1+d-1))(p(x) \boxplus p_Q(x))\\ &=(x-d)(p(x) \boxplus \underset{Q}E\,p_Q(x)), \tag{1} \end{align*} where $p_Q(x)$ is the polynomial defined by the formula $\chi_x(N_Q)=(x-(d-1))p_Q(x)$; this definition is consistent, since all the row sums of $N_Q$ equal $d-1$. By induction and the definition of $p_Q(x)$, \begin{equation*} (x-(d-1))p^{\boxplus(d-1)}(x)=\underset{Q}E\,\chi_x(N_Q) =(x-(d-1))\underset{Q}E\,p_Q(x), \end{equation*} so that $\underset{Q}E\,p_Q(x)=p^{\boxplus(d-1)}(x)$, the $(d-1)$-fold finite free convolution of $p$ with itself. Now the desired result follows by (1).