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

Marie Maccaig 1, 2, 3
3 TROPICAL - TROPICAL
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France
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.
Document type :
Journal articles
Liste complète des métadonnées

https://hal.inria.fr/hal-01423517
Contributor : Stephane Gaubert <>
Submitted on : Thursday, December 29, 2016 - 11:26:30 PM
Last modification on : Wednesday, March 27, 2019 - 4:08:32 PM

Identifiers

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⟩

Share

Metrics

Record views

182