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

Section

Original Article