Is this matrix positive semidefinite for all $n$? This is an extension of my previous question (see here). In this follow-up problem extra ones have been added in the non-diagonal matrix elements.
We want to prove the positive semi-definiteness of the $n^2\times n^2$ matrix 
$$Q=\left[\matrix{\mathbb{I}_n & e_1e_2^T+e_2e_1^T &  \cdots & e_1e_n^T+e_ne_1^T\\ e_2e_1^T+e_1e_2^T & \mathbb{I}_n & \cdots & e_2e_n^T+e_ne_2^T \\ \vdots & \vdots & \ddots & \vdots\\ e_ne_1^T+e_1e_n^T & e_ne_2^T+e_2e_n^T &\cdots & \mathbb{I}_n}\right]$$
where $\mathbb{I}_n$ is the  $n\times n$ identity matrix and $e_i$ is the $i$-th column of  $\mathbb{I}_n$. Numerical computations in MATLAB up to $n=4$ indicate that $Q$ is indeed positive semidefinite but I can't see a direct proof of this.  
Edit: This question is related to the proof of the fact 
$$\min_{\|x\|=1}\lambda\left(xx^T-\textrm{diag}(xx^T)\right)=-\frac{1}{2}$$ 
See here for details.
 A: Let $x_1\dots x_n$ be vectors in $\mathbb R^n$ with entries $x_{ij}$, denote $x=\pmatrix{x_1\\\vdots\\x_n}$. Then we have by carefull rearranging the sums
$$
\begin{split}
x^TQx & = \sum_{i=1}^n x_i^Tx_i + \sum_{i,j=1, \ i\ne j}^n (x_i^Te_i)(x_j^Te_j) + (x_i^Te_j)(x_j^Te_i)\\
& =  \sum_{i,j=1}^n x_{ij}^2 + \sum_{i,j=1, \ i\ne j}^n x_{ii}x_{jj}+x_{ij}x_{ji}\\
& = \sum_{i=1}^n x_{ii}^2+\sum_{i,j=1, \ i\ne j}^n \frac12(x_{ij}^2 + x_{ji}^2) +x_{ii}x_{jj}+x_{ij}x_{ji}\\
& =( \sum_{i=1}^n x_{ii})^2  + \frac12\sum_{i,j=1, \ i\ne j}^n (x_{ij}+x_{ji})^2,
\end{split}
$$
where one can clearly see that $Q$ is positive semi-definite. Moreover, one can immediately read-off kernel of $Q$ and the subspace on which it is positive definite.
A: The reason why $Q$ is positive semidefinite is utterly simple: it's because $Q$ is permutation-similar to a direct sum of several all-one matrices.
To prove this fact, however, we need to index the rows and columns of the partitioned matrix $Q$ by lexiographic order. This is something that one needs to get used to.
With lexiographic indices, the $(p,q)$-th row means the $q$-th row in the $p$-th block from the top. So, if $e_I$ denotes the $I$-th vector in the standard basis of $\mathbb R^{n^2}$ in lexiographic order, then we can rewrite $Q$ as
$$
\begin{bmatrix}
e_{(1,1)}e_{(1,1)}^\top+\sum\limits_{k\ne1} e_{(1,k)}e_{(1,k)}^\top
&e_{(1,1)}e_{(2,2)}^\top + e_{(1,2)}e_{(2,1)}^\top &\cdots
&e_{(1,1)}e_{(n,n)}^\top + e_{(1,n)}e_{(n,1)}^\top\\
e_{(2,2)}e_{(1,1)}^\top + e_{(2,1)}e_{(1,2)}^\top
&e_{(2,2)}e_{(2,2)}^\top+\sum\limits_{k\ne2} e_{(2,k)}e_{(2,k)}^\top &\cdots
&e_{(2,2)}e_{(n,n)}^\top + e_{(2,n)}e_{(n,2)}^\top\\
\vdots & \vdots & \ddots & \vdots\\
e_{(n,n)}e_{(1,1)}^\top + e_{(n,1)}e_{(1,n)}^\top
&e_{(n,n)}e_{(2,2)}^\top + e_{(n,2)}e_{(2,n)}^\top &\cdots
&e_{(n,n)}e_{(n,n)}^\top+\sum\limits_{k\ne n} e_{(n,k)}e_{(n,k)}^\top
\end{bmatrix}.
$$
Let $A$ denotes the set of indices $\{(1,1),(2,2),\ldots,(n,n)\}$. Also, for any $i\ne j$, let $B_{i,j}=\{(i,j),(j,i)\}$. Now one can verify that the $(I,J)$-th entry of the $\{0,1\}$-matrix $Q$ is equal to $1$ if and only if either (a) both $I,J$ belong to $A$ or (b) both $I,J$ belong to the same $B_{i,j}$. Therefore, $Q$ is the direct sum of an $n$-by-$n$ all-one matrix and $\frac12n(n-1)$ two-by-two all one matrices.
We can also obtain the eigenvalues of $Q$ immediately. They are: $n$, $2$ (of multiplicity $\frac12n(n-1)$) and $0$ (of multiplicity $(n-1)+\frac12n(n-1)$).
Edit. To illustrate, here is $Q$ when $n=4$. The ones in $Q$ are marked as $1,a,b,c,d,e,f$ and the unspecified dots are all zeros. One can see that the submatrix containing all the symbols "$1$" is a $4\times4$ all-one matrix, while the submatrix containing all the symbols "$a$" (and similarly for $b,c,d,e,f$) is a $2\times2$ all-one matrix. Since each of these submatrices is a principal submatrix of $Q$, and no two two of them share the same row or the same column, $Q$ is permutation-similar to a direct sum of them.
$$
\left[\begin{array}{cccc|cccc|cccc|cccc}
1&\cdot&\cdot&\cdot &\cdot&1&\cdot&\cdot &\cdot&\cdot&1&\cdot &\cdot&\cdot&\cdot&1\\
\cdot&a&\cdot&\cdot &a&\cdot&\cdot&\cdot &\cdot&\cdot&\cdot&\cdot &\cdot&\cdot&\cdot&\cdot\\
\cdot&\cdot&b&\cdot &\cdot&\cdot&\cdot&\cdot &b&\cdot&\cdot&\cdot &\cdot&\cdot&\cdot&\cdot\\
\cdot&\cdot&\cdot&c &\cdot&\cdot&\cdot&\cdot &\cdot&\cdot&\cdot&\cdot &c&\cdot&\cdot&\cdot\\
\hline
\cdot&a&\cdot&\cdot &a&\cdot&\cdot&\cdot &\cdot&\cdot&\cdot&\cdot &\cdot&\cdot&\cdot&\cdot\\
1&\cdot&\cdot&\cdot &\cdot&1&\cdot&\cdot &\cdot&\cdot&1&\cdot &\cdot&\cdot&\cdot&1\\
\cdot&\cdot&\cdot&\cdot &\cdot&\cdot&d&\cdot &\cdot&d&\cdot&\cdot &\cdot&\cdot&\cdot&\cdot\\
\cdot&\cdot&\cdot&\cdot &\cdot&\cdot&\cdot&e &\cdot&\cdot&\cdot&\cdot &\cdot&e&\cdot&\cdot\\
\hline
\cdot&\cdot&b&\cdot &\cdot&\cdot&\cdot&\cdot &b&\cdot&\cdot&\cdot &\cdot&\cdot&\cdot&\cdot\\
\cdot&\cdot&\cdot&\cdot &\cdot&\cdot&d&\cdot &\cdot&d&\cdot&\cdot &\cdot&\cdot&\cdot&\cdot\\
1&\cdot&\cdot&\cdot &\cdot&1&\cdot&\cdot &\cdot&\cdot&1&\cdot &\cdot&\cdot&\cdot&1\\
\cdot&\cdot&\cdot&\cdot &\cdot&\cdot&\cdot&\cdot &\cdot&\cdot&\cdot&f &\cdot&\cdot&f&\cdot\\
\hline
\cdot&\cdot&\cdot&c &\cdot&\cdot&\cdot&\cdot &\cdot&\cdot&\cdot&\cdot &c&\cdot&\cdot&\cdot\\
\cdot&\cdot&\cdot&\cdot &\cdot&\cdot&\cdot&e &\cdot&\cdot&\cdot&\cdot &\cdot&e&\cdot&\cdot\\
\cdot&\cdot&\cdot&\cdot &\cdot&\cdot&\cdot&\cdot &\cdot&\cdot&\cdot&f &\cdot&\cdot&f&\cdot\\
1&\cdot&\cdot&\cdot &\cdot&1&\cdot&\cdot &\cdot&\cdot&1&\cdot &\cdot&\cdot&\cdot&1
\end{array}\right]
$$
Edit 2. Oh, I've just discovered that Algebraic Pavel had given exactly the same answer before I posted mine, but for some curious reason he/she had deleted it.
