Advanced Search
Article Contents
Article Contents

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

Abstract Related Papers Cited by
  • 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.
    Mathematics Subject Classification: Primary: 90C22; Secondary: 06B15.


    \begin{equation} \\ \end{equation}
  • [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.


    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.


    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.


    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.


    P. Etingof, O. Golberg, S. Hensel, T. Liu, A. Schwendner, E. Udovina and D. VaintrobIntroduction to representation theory, preprint, arXiv:0901.0827v3.


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


    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.


    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.


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


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


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


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


    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.


    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.


    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.


    E. de Klerk, C. Dobre, D. V. Pasechnik and R. SotirovOn semidefinite programming relaxations of maximum k-section, Mathematical Programming-B, Online: http://link.springer.com/article/10.1007%2Fs10107-012-0603-2.


    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.


    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.


    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.


    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.


    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.


    M. Kojima, S. Kojima and S. Hara, Linear algebra for semidefinite programming, in "Research Report B-290," Tokyo Institute of Technology, (1997), 1-23.


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


    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.


    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.


    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.


    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.


    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.


    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.


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


    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.

  • 加载中

Article Metrics

HTML views() PDF downloads(136) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint