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.  doi: 10.1090/S0894-0347-07-00589-9.  Google Scholar

[2]

C. Bachoc, D. Gijswijt, A. Schrijver and F. Vallentin, Invariant semidefinite programs,, in, (2012), 219.  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.  doi: 10.1007/s11081-008-9050-6.  Google Scholar

[4]

P. J. Cameron, Coherent configurations, association schemes and permutation groups,, in, (2003), 55.   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, (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.  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.  doi: 10.1016/j.jpaa.2003.12.011.  Google Scholar

[9]

C. Godsil, "Association Schemes,", Lecture notes, (2010).   Google Scholar

[10]

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

[11]

D. G. Higman, Coherent algebras,, Linear Algebra Applications, 93 (1987), 209.  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.  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.  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.  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.  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.  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.  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.  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.  doi: 10.1007/s10107-008-0246-5.  Google Scholar

[22]

M. Kojima, S. Kojima and S. Hara, Linear algebra for semidefinite programming,, in, (1997), 1.   Google Scholar

[23]

M. Laurent, Strengthened semidefinite bounds for codes,, Mathematical Programming, 109 (2007), 239.  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.  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.  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, 3 (1978), 134.   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.  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.  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.  doi: 10.1109/TIT.2005.851748.  Google Scholar

[30]

F. Vallentin, Symmetry in semidefinite programs,, Linear Algebra and Applications, 430 (2009), 360.  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.  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.  doi: 10.1090/S0894-0347-07-00589-9.  Google Scholar

[2]

C. Bachoc, D. Gijswijt, A. Schrijver and F. Vallentin, Invariant semidefinite programs,, in, (2012), 219.  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.  doi: 10.1007/s11081-008-9050-6.  Google Scholar

[4]

P. J. Cameron, Coherent configurations, association schemes and permutation groups,, in, (2003), 55.   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, (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.  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.  doi: 10.1016/j.jpaa.2003.12.011.  Google Scholar

[9]

C. Godsil, "Association Schemes,", Lecture notes, (2010).   Google Scholar

[10]

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

[11]

D. G. Higman, Coherent algebras,, Linear Algebra Applications, 93 (1987), 209.  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.  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.  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.  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.  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.  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.  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.  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.  doi: 10.1007/s10107-008-0246-5.  Google Scholar

[22]

M. Kojima, S. Kojima and S. Hara, Linear algebra for semidefinite programming,, in, (1997), 1.   Google Scholar

[23]

M. Laurent, Strengthened semidefinite bounds for codes,, Mathematical Programming, 109 (2007), 239.  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.  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.  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, 3 (1978), 134.   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.  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.  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.  doi: 10.1109/TIT.2005.851748.  Google Scholar

[30]

F. Vallentin, Symmetry in semidefinite programs,, Linear Algebra and Applications, 430 (2009), 360.  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.  doi: 10.1112/plms/s2-6.1.77.  Google Scholar

[1]

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

Ville Salo, Ilkka Törmä. Recoding Lie algebraic subshifts. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 1005-1021. doi: 10.3934/dcds.2020307
[3]

Evan Greif, Daniel Kaplan, Robert S. Strichartz, Samuel C. Wiese. Spectrum of the Laplacian on regular polyhedra. Communications on Pure & Applied Analysis, 2021, 20 (1) : 193-214. doi: 10.3934/cpaa.2020263
[4]

Hongliang Chang, Yin Chen, Runxuan Zhang. A generalization on derivations of Lie algebras. Electronic Research Archive, , () : -. doi: 10.3934/era.2020124
[5]

Yongjie Wang, Nan Gao. Some properties for almost cellular algebras. Electronic Research Archive, 2021, 29 (1) : 1681-1689. doi: 10.3934/era.2020086
[6]

Yicheng Liu, Yipeng Chen, Jun Wu, Xiao Wang. Periodic consensus in network systems with general distributed processing delays. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2021002
[7]

Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020463
[8]

Simon Hochgerner. Symmetry actuated closed-loop Hamiltonian systems. Journal of Geometric Mechanics, 2020, 12 (4) : 641-669. doi: 10.3934/jgm.2020030
[9]

Anh Tuan Duong, Phuong Le, Nhu Thang Nguyen. Symmetry and nonexistence results for a fractional Choquard equation with weights. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 489-505. doi: 10.3934/dcds.2020265
[10]

Lucio Damascelli, Filomena Pacella. Sectional symmetry of solutions of elliptic systems in cylindrical domains. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3305-3325. doi: 10.3934/dcds.2020045
[11]

Peizhao Yu, Guoshan Zhang, Yi Zhang. Decoupling of cubic polynomial matrix systems. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 13-26. doi: 10.3934/naco.2020012
[12]

Shengxin Zhu, Tongxiang Gu, Xingping Liu. AIMS: Average information matrix splitting. Mathematical Foundations of Computing, 2020, 3 (4) : 301-308. doi: 10.3934/mfc.2020012
[13]

Kerioui Nadjah, Abdelouahab Mohammed Salah. Stability and Hopf bifurcation of the coexistence equilibrium for a differential-algebraic biological economic system with predator harvesting. Electronic Research Archive, 2021, 29 (1) : 1641-1660. doi: 10.3934/era.2020084
[14]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054
[15]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102
[16]

Pablo Neme, Jorge Oviedo. A note on the lattice structure for matching markets via linear programming. Journal of Dynamics & Games, 2020  doi: 10.3934/jdg.2021001
[17]

Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021012
[18]

Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial & Management Optimization, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136
[19]

Lihong Zhang, Wenwen Hou, Bashir Ahmad, Guotao Wang. Radial symmetry for logarithmic Choquard equation involving a generalized tempered fractional $ p $-Laplacian. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020445
[20]

Chunming Tang, Maozhi Xu, Yanfeng Qi, Mingshuo Zhou. A new class of $ p $-ary regular bent functions. Advances in Mathematics of Communications, 2021, 15 (1) : 55-64. doi: 10.3934/amc.2020042

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences