Algorithms and Properties for Positive Symmetrizable Matrices

Elisângela Silva Dias, Diane Castonguay, Mitre Costa Dourado

Abstract


Matrices are the most common representations of graphs. They are also used for representing algebras and cluster algebras. This paper shows some properties of matrices in order to facilitate the understanding of symmetrizable matrices with specific characteristics, called positive quasi-Cartan companion matrices, and the problem of localizing them. Here, symmetrizable matrices are those which are symmetric when multiplied by a diagonal matrix with positive entries called symmetrizer matrix. We conjecture that this problem is NP-complete and we show that it is in NP by generalizing Sylvester's criterion for symmetrizable matrices. We straighten known coefficient limits for such matrices.

Keywords


Symmetrizable matrix; positive quasi-Cartan matrix; algorithm.

Full Text:

PDF

References


M. Barot, C. Geiss, A. Zelevinsky, Cluster algebras of finite type and positive symmetrizable matrices, J. London Math. Soc., 73 (2006), 545--564.

T.H. Cormen, C.E. Leiserson, C. Stein, R.L. Rivest, Introduction to Algorithms, The Mit Press-id, 2nd edition, 2002.

C.J. Colbourn, B.D. McKay, A corretion to Colbourn's paper on the complexity of matrix symmetrizability, Inform. Proc. Letters, 11 (1980), 96--97.

S. Fomin, A. Zelevinsky, Cluster algebras I: Foundations, J. Amer. Math. Soc.}, 15, No. 2 (2002) 2, 497--529 (electronic).

S. Fomin, A. Zelevinsky, Cluster algebras II: finite type classification, Invent. Math., 154 (2003), 63--121.

E.L. Lima, Álgebra Linear, Associação Instituto Nacional de Matemática Pura e Aplicada, Rio de Janeiro, Coleção Matemática Universitária, 6th edition, 2003.

Ghorpade, S.R.; Limaye, B.V: Sylvester's Minorant Criterion, Lagrange-Beltrami Identity and Nonnegative Definiteness. Math. Student, Special Centenary, 123--130 (2007).

M. Sipser, Introduction to the Theory of Computation, Thomson, 2nd edition, 2006.

Chen, Wai-Kai: Theory and Design of Broadband Matching Networks, Pergamon Press Ltd., 1976.




DOI: https://doi.org/10.5540/tema.2016.017.02.0187

Article Metrics

Metrics Loading ...

Metrics powered by PLOS ALM

Refbacks

  • There are currently no refbacks.


Trends in Computational and Applied Mathematics

A publication of the Brazilian Society of Applied and Computational Mathematics (SBMAC)

 

Indexed in:

                       

         

 

Desenvolvido por:

Logomarca da Lepidus Tecnologia