Mathematical properties of the regular *-representation of matrix $*$-algebras with applications to semidefinite programming

Cristian Dobre

doi:10.3934/naco.2013.3.367

Article Contents

2013, Volume 3, Issue 2: 367-378. Doi: 10.3934/naco.2013.3.367

This issue Previous Article Weak and strong convergence of prox-penalization and splitting algorithms for bilevel equilibrium problems Next Article Index-range monotonicity and index-proper splittings of matrices

Mathematical properties of the regular -representation of matrix $$-algebras with applications to semidefinite programming

Cristian Dobre^1,

1.
Johann Bernoulli Institute for Mathematics and Computer Science, University of Groningen, Groningen

Received: May 31, 2011

Revised: October 31, 2012

Published: March 2013

Abstract Related Papers Cited by

Abstract

In this paper we give a proof for the special structure of the Wedderburn decomposition of the regular *-representation of a given matrix $*$-algebra. This result was stated without proof in: de Klerk, E., Dobre, C. and Pasechnik, D.V.: Numerical block diagonalization of matrix $*$-algebras with application to semidefinite programming, Mathematical Programming-B, 129 (2011), 91--111; and is used in applications of semidefinite programming (SDP) for structured combinatorial optimization problems. In order to provide the proof for this special structure we derive several other mathematical properties of the regular *-representation.

Keywords:

Mathematics Subject Classification: Primary: 90C22; Secondary: 06B15.

Citation:

Related Papers

Cited by

References

[1]	C. Bachoc and F. Vallentin, New upper bounds for kissing numbers from semidefinite programming, J. Amer. Math. Soc., 21 (2008), 909-924.doi: 10.1090/S0894-0347-07-00589-9.
[2]	C. Bachoc, D. Gijswijt, A. Schrijver and F. Vallentin, Invariant semidefinite programs, in "Handbook on Semidefinite, Conic and Polynomial Optimization" (eds. M. F. Anjos and J. B. Lasserre), Springer, (2012), 219-270.doi: 10.1007/978-1-4614-0769-0_9.
[3]	Y.-Q. Bai, E. de Klerk, D. V. Pasechnik and R. Sotirov, Exploiting group symmetry in truss topology optimization, Optimization and Engineering, 10 (2009), 331-349.doi: 10.1007/s11081-008-9050-6.
[4]	P. J. Cameron, Coherent configurations, association schemes and permutation groups, in "Groups, Combinatorics and Geometry" (eds. A.A. Ivanov, M.W. Liebeck and J. Saxl), World Scientific, Singapore, (2003), 55-71.
[5]	P. Etingof, O. Golberg, S. Hensel, T. Liu, A. Schwendner, E. Udovina and D. Vaintrob, Introduction to representation theory, preprint, arXiv:0901.0827v3.
[6]	D. Gijswijt, "Matrix Algebras and Semidefinite Programming Techniques for Codes," Ph. D. Thesis, University of Amsterdam, The Netherlands, 2005.
[7]	D. Gijswijt, A. Schrijver and H. Tanaka, New upper bounds for nonbinary codes based on the Terwilliger algebra and semidefinite programming, Journal of Combinatorial Theory, 113 (2006), 1719-1731.doi: 10.1016/j.jcta.2006.03.010.
[8]	K. Gatermann and P. A. Parrilo, Symmetry groups, semidefinite programs, and sums of squares, J. Pure and Applied Algebra, 192 (2004), 95-128.doi: 10.1016/j.jpaa.2003.12.011.
[9]	C. Godsil, "Association Schemes," Lecture notes, University of Waterloo, 2010. Available from: http://quoll.uwaterloo.ca/mine/Notes/assoc2.pdf.
[10]	A. Graham, "Kroneker Products and Matrix Calculus with Applications," John Wiley and Sons, Chichester, 1981.doi: ISBN-13/978-0-4702-7300-5.
[11]	D. G. Higman, Coherent algebras, Linear Algebra Applications, 93 (1987), 209-239.doi: 10.1016/S0024-3795(87)90326-0.
[12]	R. A. Horn and C. R. Johnson, "Matrix Analysis," Cambridge University Press, 1990.doi: ISBN-13/978-0-5213-8632-6.
[13]	Y. Kanno, M. Ohsaki, K. Murota and N. Katoh, Group symmetry in interior-point methods for semidefinite program, Optimization and Engineering, 2 (2001), 293-320.doi: 10.1023/A:1015366416311.
[14]	E. de Klerk, Exploiting special structure in semidefinite programming: a survey, of theory and applications, European Journal of Operational Research, 201 (2010), 1-10.doi: 10.1016/j.ejor.2009.01.025.
[15]	E. de Klerk, C. Dobre and D. V. Pasechnik, Numerical block diagonalization of matrix -algebras with application to semidefinite programming, Mathematical Programming-B, 129* (2011), 91-111.doi: 10.1007/s10107-011-0461-3.
[16]	E. de Klerk, C. Dobre, D. V. Pasechnik and R. Sotirov, On semidefinite programming relaxations of maximum k-section, Mathematical Programming-B, Online: http://link.springer.com/article/10.1007%2Fs10107-012-0603-2.
[17]	E. de Klerk and C. Dobre, A comparison of lower bounds for the Symmetric Circulant Traveling Salseman Problem, Discrete Applied Mathematics, 159 (2011), 1815-1826.doi: 10.1016/j.dam.2011.01.026.
[18]	E. de Klerk, D. V. Pasechnik and A. Schrijver, Reduction of symmetric semidefinite programs using the regular -representation, Mathematical Programming-B, 109* (2007), 613-624.doi: 10.1007/s10107-006-0039-7.
[19]	E. de Klerk, M. W. Newman, D. V. Pasechnik and R. Sotirov, On the Lovász $\vartheta$-number of almost regular graphs with application to Erdös-Rényi graphs, European Journal of Combinatorics, 31 (2009), 879-888.doi: 10.1016/j.ejc.2008.07.022.
[20]	E. de Klerk, J. Maharry, D. V. Pasechnik, B. Richter and G. Salazar, Improved bounds for the crossing numbers of k_m,n and k_n, SIAM Journal on Discrete Mathematics, 20 (2006), 189-202.doi: 10.1137/S0895480104442741.
[21]	E. de Klerk and R. Sotirov, Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem, Mathematical Programming, 122 (2010), 225-246.doi: 10.1007/s10107-008-0246-5.
[22]	M. Kojima, S. Kojima and S. Hara, Linear algebra for semidefinite programming, in "Research Report B-290," Tokyo Institute of Technology, (1997), 1-23.
[23]	M. Laurent, Strengthened semidefinite bounds for codes, Mathematical Programming, 109 (2007), 239-261.doi: 10.1007/s10107-006-0030-3.
[24]	L. Lovász, On the Shannon capacity of a graph, IEEE Transactions on Information theory, 25 (1979), 1-7.doi: 10.1109/TIT.1979.1055985.
[25]	T. Maehara and K. Murota, A numerical algorithm for block-diagonal decomposition of matrix -algebras with general irreducible components*, Japan Journal of Industrial and Applied Mathematics, 27 (2010), 263-293.doi: 10.1007/s13160-010-0007-8.
[26]	R. J. McEliece, E. R. Rodemich and H. C. Rumsey, The Lovász bound and some generalizations, Journal of Combinatorics, Information & System Sciences, 3 (1978), 134-152.
[27]	K. Murota, Y. Kanno, M. Kojima and S. Kojima, A numerical algorithm for block-diagonal decomposition of matrix -algebras with application to semidefinite programming*, Japan Journal of Industrial and Applied Mathematics, 27 (2010), 125-160.doi: 10.1007/s13160-010-0006-9.
[28]	A. Schrijver, A comparison of the Delsarte and Lovász bounds, IEEE Transactions on Information Theory, 25 (1979), 425-429.doi: 10.1109/TIT.1979.1056072.
[29]	A. Schrijver, New code upper bounds from the Terwilliger algebra, IEEE Transactions on Information Theory, 51 (2005), 2859-2866.doi: 10.1109/TIT.2005.851748.
[30]	F. Vallentin, Symmetry in semidefinite programs, Linear Algebra and Applications, 430 (2009), 360-369.doi: 10.1016/j.laa.2008.07.025.
[31]	J. H. M. Wedderburn, On hypercomplex numbers, Proceedings of the London Mathematical Society, 6 (1907), 77-118.doi: 10.1112/plms/s2-6.1.77.