Algorithms and Properties for Positive Symmetrizable Matrices

Authors

  • Elisângela Silva Dias Universidade Federal de Goiás http://orcid.org/0000-0002-1132-1518
  • Diane Castonguay Universidade Federal de Goiás
  • Mitre Costa Dourado Universidade Federal do Rio de Janeiro

DOI:

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

Keywords:

Symmetrizable matrix, positive quasi-Cartan matrix, algorithm.

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.

Author Biography

Elisângela Silva Dias, Universidade Federal de Goiás

Instituto de Informática

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.

Downloads

Published

2016-09-04

How to Cite

Dias, E. S., Castonguay, D., & Dourado, M. C. (2016). Algorithms and Properties for Positive Symmetrizable Matrices. Trends in Computational and Applied Mathematics, 17(2), 187. https://doi.org/10.5540/tema.2016.017.02.0187

Issue

Vol. 17 No. 2 (2016)

Section

Original Article

License

Copyright

Authors of articles published in the journal Trends in Computational and Applied Mathematics retain the copyright of their work. The journal uses Creative Commons Attribution (CC-BY) in published articles. The authors grant the TCAM journal the right to first publish the article.

Intellectual Property and Terms of Use

The content of the articles is the exclusive responsibility of the authors. The journal uses Creative Commons Attribution (CC-BY) in published articles. This license allows published articles to be reused without permission for any purpose as long as the original work is correctly cited.

The journal encourages Authors to self-archive their accepted manuscripts, publishing them on personal blogs, institutional repositories, and social media, as long as the full citation is included in the journal's website version.