Reduction of symmetric semidefinite programs using the regular ast-representation

We consider semidefinite programming problems on which a permutation group is acting. We describe a general technique to reduce the size of such problems, exploiting the symmetry. The technique is based on a low-order matrix $*$ -representation of the commutant (centralizer ring) of the matrix algebra generated by the permutation matrices. We apply it to extending a method of de Klerk et al. that gives a semidefinite programming lower bound to the crossing number of complete bipartite graphs. It implies that cr(K _8,n ) ≥ 2.9299n ² ? 6n, cr(K _9,n ) ≥ 3.8676n ² ? 8n, and (for any m ≥ 9) $$lim_{ntoinfty}frac{{rm cr}(K_{m,n})}{Z(m,n)}geq 0.8594frac{m}{m-1},$$ where Z(m,n) is the Zarankiewicz number $lfloorfrac{1}{4}(m-1)^2rfloorlfloorfrac{1}{4}(n-1)^2rfloor$ , which is the conjectured value of cr(K _m,n ). Here the best factor previously known was 0.8303 instead of 0.8594.