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

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

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

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

Received June 2011 Revised November 2012 Published April 2013

Abstract
Related Papers

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.
[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.
[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.
[4]	P. J. Cameron, Coherent configurations, association schemes and permutation groups,, in, (2003), 55.
[5]	P. Etingof, O. Golberg, S. Hensel, T. Liu, A. Schwendner, E. Udovina and D. Vaintrob, Introduction to representation theory, preprint,, , ().
[6]	D. Gijswijt, "Matrix Algebras and Semidefinite Programming Techniques for Codes,", Ph. D. Thesis, (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. 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. doi: 10.1016/j.jpaa.2003.12.011.
[9]	C. Godsil, "Association Schemes,", Lecture notes, (2010).
[10]	A. Graham, "Kroneker Products and Matrix Calculus with Applications,", John Wiley and Sons, (1981). doi: ISBN-13/978-0-4702-7300-5.
[11]	D. G. Higman, Coherent algebras,, Linear Algebra Applications, 93 (1987), 209. 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. 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. 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. 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, (): 10107.
[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.
[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.
[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.
[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. 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. doi: 10.1007/s10107-008-0246-5.
[22]	M. Kojima, S. Kojima and S. Hara, Linear algebra for semidefinite programming,, in, (1997), 1.
[23]	M. Laurent, Strengthened semidefinite bounds for codes,, Mathematical Programming, 109 (2007), 239. 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. 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. 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, 3 (1978), 134.
[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.
[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.
[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.
[30]	F. Vallentin, Symmetry in semidefinite programs,, Linear Algebra and Applications, 430 (2009), 360. 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. 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. doi: 10.1090/S0894-0347-07-00589-9.
[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.
[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.
[4]	P. J. Cameron, Coherent configurations, association schemes and permutation groups,, in, (2003), 55.
[5]	P. Etingof, O. Golberg, S. Hensel, T. Liu, A. Schwendner, E. Udovina and D. Vaintrob, Introduction to representation theory, preprint,, , ().
[6]	D. Gijswijt, "Matrix Algebras and Semidefinite Programming Techniques for Codes,", Ph. D. Thesis, (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. 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. doi: 10.1016/j.jpaa.2003.12.011.
[9]	C. Godsil, "Association Schemes,", Lecture notes, (2010).
[10]	A. Graham, "Kroneker Products and Matrix Calculus with Applications,", John Wiley and Sons, (1981). doi: ISBN-13/978-0-4702-7300-5.
[11]	D. G. Higman, Coherent algebras,, Linear Algebra Applications, 93 (1987), 209. 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. 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. 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. 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, (): 10107.
[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.
[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.
[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.
[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. 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. doi: 10.1007/s10107-008-0246-5.
[22]	M. Kojima, S. Kojima and S. Hara, Linear algebra for semidefinite programming,, in, (1997), 1.
[23]	M. Laurent, Strengthened semidefinite bounds for codes,, Mathematical Programming, 109 (2007), 239. 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. 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. 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, 3 (1978), 134.
[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.
[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.
[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.
[30]	F. Vallentin, Symmetry in semidefinite programs,, Linear Algebra and Applications, 430 (2009), 360. 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. doi: 10.1112/plms/s2-6.1.77.

[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]	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
[4]	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
[5]	Jiani Wang, Liwei Zhang. Statistical inference of semidefinite programming with multiple parameters. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-12. doi: 10.3934/jimo.2019015
[6]	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
[7]	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
[8]	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
[9]	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
[10]	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
[11]	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
[12]	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
[13]	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
[14]	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
[15]	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
[16]	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
[17]	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
[18]	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
[19]	Hui Zhang, Jian-Feng Cai, Lizhi Cheng, Jubo Zhu. Strongly convex programming for exact matrix completion and robust principal component analysis. Inverse Problems & Imaging, 2012, 6 (2) : 357-372. doi: 10.3934/ipi.2012.6.357
[20]	R. Enkhbat, T. V. Gruzdeva, M. V. Barkova. D.C. programming approach for solving an applied ore-processing problem. Journal of Industrial & Management Optimization, 2018, 14 (2) : 613-623. doi: 10.3934/jimo.2017063

Impact Factor:

American Institute of Mathematical Sciences