Let $B$ be a square 0-1 matrix and there exists no permutation matrices $P_1$ and $P_2$ such that $\mathrm{tr}(P_2^TBP_1)=n$. Then show that $B$ does not have full rank.
Somehow I think the proof is related to being able to write matrix as a linear combination of permutation matrices.
Best Answer
This isn't true. Consider e.g. $n=2$ and $B=\pmatrix{0&1\\ 1&0}$. Using the tracial property, we have $\operatorname{tr}(P^TBP)=\operatorname{tr}(PP^TB)=\operatorname{tr}(B)=0\ne n$, but $B$ has full rank.
The statement can be corrected by requiring that $\operatorname{tr}(BP)\ne n$ for all permutation matrices $P$ (or equivalently, $\operatorname{tr}(P_2^TBP_1)\ne n$ for all permutation matrices $P_1$ and $P_2$, because $\operatorname{tr}(P_2^TBP_1)=\operatorname{tr}(BP_1P_2^T)$ and $P_1P_2^T$ is a permutation matrix). This means $\sum_ib_{i\sigma(i)}\ne n$ for all permutations $\sigma$. Since $B$ is a $0-1$ matrix, $\sum_ib_{i\sigma(i)}\ne n$ only if $b_{i\sigma(i)}=0$ for some $i$. Therefore $\det(B)=\sum_\sigma\operatorname{sgn}(\sigma)\prod_ib_{i\sigma(i)}=0$, i.e. $B$ is singular.