On scaling to an integer matrix and graphs with integer weighted cycles

Abstract : Between 1970 and 1982 Hans Schneider and co-authors produced a number of results regarding matrix scalings. They demonstrated that a matrix has a diagonal similarity scaling to any matrix with entries in the subgroup generated by the cycle weights of the associated digraph, and that a matrix has an equivalent scaling to any matrix with entries related to the weights of cycles in an associated bipartite graph. Further, given matrices A and B, they produced a description of all diagonal X such that X−1AX=B. In 2005 Butkovič and Schneider used max-algebra to give a simple and efficient description of this set of scalings. In this paper we focus on the additive group of integers, and work in the max-plus algebra to give a full description of all scalings of a real matrix A to any integer matrix. We do this for four types of scalings; beginning with the familiar X−1AX, XAY and XAX scalings and finishing with a new scaling which we call a signed similarity scaling. This is a scaling of the form XAY where we specify for each row i , either xi=yi or xi=−yi. In all of our results we use necessary and sufficient conditions for existence which are based on integer weighted cycles in the associated digraph, or associated bipartite graph, of the matrix.
Type de document :
Article dans une revue
Linear Algebra and Applications, Elsevier - Academic Press, 2016, 498, pp.490--520. 〈10.1016/j.laa.2016.01.018〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01423517
Contributeur : Stephane Gaubert <>
Soumis le : jeudi 29 décembre 2016 - 23:26:30
Dernière modification le : jeudi 10 mai 2018 - 02:05:38

Identifiants

Citation

Marie Maccaig. On scaling to an integer matrix and graphs with integer weighted cycles. Linear Algebra and Applications, Elsevier - Academic Press, 2016, 498, pp.490--520. 〈10.1016/j.laa.2016.01.018〉. 〈hal-01423517〉

Partager

Métriques

Consultations de la notice

154