American Institute of Mathematical Sciences

Advanced
2013, 3(2): 367-378. doi: 10.3934/naco.2013.3.367

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, Netherlands

Received  June 2011 Revised  November 2012 Published  April 2013

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: regular *-representation, algebraic symmetry, pre-processing, semidefinite programming, Matrix algebras.
Mathematics Subject Classification: Primary: 90C22; Secondary: 06B1.
Citation: Cristian Dobre. Mathematical properties of the regular *-representation of matrix $*$-algebras with applications to semidefinite programming. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 367-378. doi: 10.3934/naco.2013.3.367
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 km,n and kn, 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.

show all references

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 km,n and kn, 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.

[1]

Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial and Management Optimization, 2010, 6 (4) : 881-893. doi: 10.3934/jimo.2010.6.881
[2]

Adel Alahmadi, Hamed Alsulami, S.K. Jain, Efim Zelmanov. On matrix wreath products of algebras. Electronic Research Announcements, 2017, 24: 78-86. doi: 10.3934/era.2017.24.009
[3]

Doston Jumaniyozov, Ivan Kaygorodov, Abror Khudoyberdiyev. The algebraic classification of nilpotent commutative algebras. Electronic Research Archive, 2021, 29 (6) : 3909-3993. doi: 10.3934/era.2021068
[4]

Jiani Wang, Liwei Zhang. Statistical inference of semidefinite programming with multiple parameters. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1527-1538. doi: 10.3934/jimo.2019015
[5]

Daniel Heinlein, Ferdinand Ihringer. New and updated semidefinite programming bounds for subspace codes. Advances in Mathematics of Communications, 2020, 14 (4) : 613-630. doi: 10.3934/amc.2020034
[6]

Shouhong Yang. Semidefinite programming via image space analysis. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1187-1197. doi: 10.3934/jimo.2016.12.1187
[7]

Christine Bachoc, Alberto Passuello, Frank Vallentin. Bounds for projective codes from semidefinite programming. Advances in Mathematics of Communications, 2013, 7 (2) : 127-145. doi: 10.3934/amc.2013.7.127
[8]

Gökhan Mutlu. On the quotient quantum graph with respect to the regular representation. Communications on Pure and Applied Analysis, 2021, 20 (2) : 885-902. doi: 10.3934/cpaa.2020295
[9]

Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193
[10]

Joshua Du, Jun Ji. An integral representation of the determinant of a matrix and its applications. Conference Publications, 2005, 2005 (Special) : 225-232. doi: 10.3934/proc.2005.2005.225
[11]

L. Bakker. A reducible representation of the generalized symmetry group of a quasiperiodic flow. Conference Publications, 2003, 2003 (Special) : 68-77. doi: 10.3934/proc.2003.2003.68
[12]

Liming Ling. The algebraic representation for high order solution of Sasa-Satsuma equation. Discrete and Continuous Dynamical Systems - S, 2016, 9 (6) : 1975-2010. doi: 10.3934/dcdss.2016081
[13]

Grégory Berhuy. Algebraic space-time codes based on division algebras with a unitary involution. Advances in Mathematics of Communications, 2014, 8 (2) : 167-189. doi: 10.3934/amc.2014.8.167
[14]

Min-Fan He, Li-Ning Xing, Wen Li, Shang Xiang, Xu Tan. Double layer programming model to the scheduling of remote sensing data processing tasks. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1515-1526. doi: 10.3934/dcdss.2019104
[15]

Wei-guo Wang, Wei-chao Wang, Ren-cang Li. Deflating irreducible singular M-matrix algebraic Riccati equations. Numerical Algebra, Control and Optimization, 2013, 3 (3) : 491-518. doi: 10.3934/naco.2013.3.491
[16]

Rui Qian, Rong Hu, Ya-Ping Fang. Local smooth representation of solution sets in parametric linear fractional programming problems. Numerical Algebra, Control and Optimization, 2019, 9 (1) : 45-52. doi: 10.3934/naco.2019004
[17]

Yang Li, Yonghong Ren, Yun Wang, Jian Gu. Convergence analysis of a nonlinear Lagrangian method for nonconvex semidefinite programming with subproblem inexactly solved. Journal of Industrial and Management Optimization, 2015, 11 (1) : 65-81. doi: 10.3934/jimo.2015.11.65
[18]

Yang Li, Liwei Zhang. A nonlinear Lagrangian method based on Log-Sigmoid function for nonconvex semidefinite programming. Journal of Industrial and Management Optimization, 2009, 5 (3) : 651-669. doi: 10.3934/jimo.2009.5.651
[19]

Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial and Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117
[20]

Jiang-Xia Nan, Deng-Feng Li. Linear programming technique for solving interval-valued constraint matrix games. Journal of Industrial and Management Optimization, 2014, 10 (4) : 1059-1070. doi: 10.3934/jimo.2014.10.1059

 Impact Factor: 

Tools

Metrics

  • PDF downloads (114)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy