A question about finite free convolution For any square matrix $Y$ let $\chi_x(Y) = det(xI -Y)$ denote its characteristic polynomial. 
Say $A$ and $B$ are two $n-$dimensional symmetric matrices with constant row sums $a$ and $b$. Lets define the polynomials $p_1(x)$ and $p_2(x)$ as follows : $\chi_x(A)=(x-a)p_1(x)$ and $\chi_x(B)=(x-b)p_2(x)$. Then over uniform sampling from the permutation group $S_n$ one can show (quite a non-trivial proof) that ``finite free convolution" (denoted as $\boxplus$) satisfies the following identity,
$$\mathbb{E}_{P \sim S_n} [\chi_x(A + PBP^T)] = (x-(a+b))[p_1(x) \boxplus p_2(x)]$$
Given a $n-$dimensional symmetric matrix $M$ such that, $\chi_x(M) = (x-1)^{\frac {n}{2}}(x+1)^{\frac {n}{2}}$ define a polynomial $p$ such that $\chi_x(M)=(x-1)p(x)$. Now apparently the following identity holds for any positive integer $d$, 
$$\underset{P_1,P_2,..,P_d \sim S_n}{\mathbb{E}}[\chi_x(P_1MP_1^T+ P_2MP_2^T+..+P_dMP_d^T)]\\
 = (x-d)[p(x)\boxplus p(x) ..(d \text{  times})..\boxplus p(x)]$$
Can someone kindly help derive the second equality from the first? 

I believe this is some kind of an induction but I am unable to get it work. As in even at $d=3$ I cant get this explicitly. 
 A: 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). 
