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 & 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5]

P. Etingof, O. Golberg, S. Hensel, T. Liu, A. Schwendner, E. Udovina and D. Vaintrob, Introduction to representation theory, preprint,, , ().   Google Scholar

[6]

D. Gijswijt, "Matrix Algebras and Semidefinite Programming Techniques for Codes," Ph. D. Thesis, University of Amsterdam, The Netherlands, 2005. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[9]

C. Godsil, "Association Schemes," Lecture notes, University of Waterloo, 2010. Available from: http://quoll.uwaterloo.ca/mine/Notes/assoc2.pdf. Google Scholar

[10]

A. Graham, "Kroneker Products and Matrix Calculus with Applications," John Wiley and Sons, Chichester, 1981. doi: ISBN-13/978-0-4702-7300-5.  Google Scholar

[11]

D. G. Higman, Coherent algebras, Linear Algebra Applications, 93 (1987), 209-239. doi: 10.1016/S0024-3795(87)90326-0.  Google Scholar

[12]

R. A. Horn and C. R. Johnson, "Matrix Analysis," Cambridge University Press, 1990. doi: ISBN-13/978-0-5213-8632-6.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[16]

E. de Klerk, C. Dobre, D. V. Pasechnik and R. Sotirov, On semidefinite programming relaxations of maximum k-section,, Mathematical Programming-B, (): 10107.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[23]

M. Laurent, Strengthened semidefinite bounds for codes, Mathematical Programming, 109 (2007), 239-261. doi: 10.1007/s10107-006-0030-3.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[30]

F. Vallentin, Symmetry in semidefinite programs, Linear Algebra and Applications, 430 (2009), 360-369. doi: 10.1016/j.laa.2008.07.025.  Google Scholar

[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.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5]

P. Etingof, O. Golberg, S. Hensel, T. Liu, A. Schwendner, E. Udovina and D. Vaintrob, Introduction to representation theory, preprint,, , ().   Google Scholar

[6]

D. Gijswijt, "Matrix Algebras and Semidefinite Programming Techniques for Codes," Ph. D. Thesis, University of Amsterdam, The Netherlands, 2005. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[9]

C. Godsil, "Association Schemes," Lecture notes, University of Waterloo, 2010. Available from: http://quoll.uwaterloo.ca/mine/Notes/assoc2.pdf. Google Scholar

[10]

A. Graham, "Kroneker Products and Matrix Calculus with Applications," John Wiley and Sons, Chichester, 1981. doi: ISBN-13/978-0-4702-7300-5.  Google Scholar

[11]

D. G. Higman, Coherent algebras, Linear Algebra Applications, 93 (1987), 209-239. doi: 10.1016/S0024-3795(87)90326-0.  Google Scholar

[12]

R. A. Horn and C. R. Johnson, "Matrix Analysis," Cambridge University Press, 1990. doi: ISBN-13/978-0-5213-8632-6.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[16]

E. de Klerk, C. Dobre, D. V. Pasechnik and R. Sotirov, On semidefinite programming relaxations of maximum k-section,, Mathematical Programming-B, (): 10107.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[23]

M. Laurent, Strengthened semidefinite bounds for codes, Mathematical Programming, 109 (2007), 239-261. doi: 10.1007/s10107-006-0030-3.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[30]

F. Vallentin, Symmetry in semidefinite programs, Linear Algebra and Applications, 430 (2009), 360-369. doi: 10.1016/j.laa.2008.07.025.  Google Scholar

[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.  Google Scholar

[1]

Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial & 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]

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

Jiani Wang, Liwei Zhang. Statistical inference of semidefinite programming with multiple parameters. Journal of Industrial & 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 & 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]

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

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
[10]

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
[11]

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

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
[13]

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 & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1515-1526. doi: 10.3934/dcdss.2019104
[14]

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

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

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 & Management Optimization, 2015, 11 (1) : 65-81. doi: 10.3934/jimo.2015.11.65
[17]

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

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

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

Yaguang Huangfu, Guanqing Liang, Jiannong Cao. MatrixMap: Programming abstraction and implementation of matrix computation for big data analytics. Big Data & Information Analytics, 2016, 1 (4) : 349-376. doi: 10.3934/bdia.2016015

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences