Testing the irreducibility of nonsquare Perron-Frobenius systems

C. Avin; M. Borokhovich; Y. Haddad; E. Kantor; Z. Lotker; Merav Parter; David Peleg

doi:10.1016/j.ipl.2014.05.004

Testing the irreducibility of nonsquare Perron-Frobenius systems

C. Avin, M. Borokhovich, Y. Haddad, E. Kantor, Z. Lotker, Merav Parter, David Peleg

Department of Computer Science and Applied Mathematics

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

Abstract

The Perron-Frobenius (PF) theorem provides a simple characterization of the eigenvectors and eigenvalues of irreducible nonnegative square matrices. A generalization of the PF theorem to nonsquare matrices, which can be interpreted as representing systems with additional degrees of freedom, was recently presented in [1]. This generalized theorem requires a notion of irreducibility for nonsquare systems. A suitable definition, based on the property that every maximal square (legal) subsystem is irreducible, is provided in [1], and is shown to be necessary and sufficient for the generalized theorem to hold. This note shows that irreducibility of a nonsquare system can be tested in polynomial time. The analysis uses a graphic representation of the nonsquare system, termed the constraint graph, representing the flow of influence between the constraints of the system.

Original language	English
Pages (from-to)	728-733
Number of pages	6
Journal	Information Processing Letters
Volume	114
Issue number	12
DOIs	https://doi.org/10.1016/j.ipl.2014.05.004
Publication status	Published - Dec 2014

Funding

Eshkol fellowship, Israel Ministry of Science and Technology; Israel Science Foundation [894/09]; Israel PBC [4/11]; Israel ISF [4/11]; United States-Israel Binational Science Foundation [2008348]; Israel Ministry of Science and Technology [6478]; Citigroup Foundation; Google Europe Fellowship; Google FellowshipSupported by Eshkol fellowship, the Israel Ministry of Science and Technology.Supported by a grant of the Israel Science Foundation.Supported in part by the Israel Science Foundation (grant 894/09), the I-CORE program of the Israel PBC and ISF (grant 4/11), the United States-Israel Binational Science Foundation (grant 2008348), the Israel Ministry of Science and Technology (infrastructures grant 6478), and the Citigroup Foundation.Recipient of the Google Europe Fellowship in distributed computing; research supported in part by this Google Fellowship.

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Information Systems
Signal Processing
Computer Science Applications

Access to Document

10.1016/j.ipl.2014.05.004

Cite this

@article{65bb284d617d49f38dd70f2693cc0952,

title = "Testing the irreducibility of nonsquare Perron-Frobenius systems",

abstract = "The Perron-Frobenius (PF) theorem provides a simple characterization of the eigenvectors and eigenvalues of irreducible nonnegative square matrices. A generalization of the PF theorem to nonsquare matrices, which can be interpreted as representing systems with additional degrees of freedom, was recently presented in [1]. This generalized theorem requires a notion of irreducibility for nonsquare systems. A suitable definition, based on the property that every maximal square (legal) subsystem is irreducible, is provided in [1], and is shown to be necessary and sufficient for the generalized theorem to hold. This note shows that irreducibility of a nonsquare system can be tested in polynomial time. The analysis uses a graphic representation of the nonsquare system, termed the constraint graph, representing the flow of influence between the constraints of the system.",

author = "C. Avin and M. Borokhovich and Y. Haddad and E. Kantor and Z. Lotker and Merav Parter and David Peleg",

year = "2014",

month = dec,

doi = "10.1016/j.ipl.2014.05.004",

language = "English",

volume = "114",

pages = "728--733",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "12",

}

TY - JOUR

T1 - Testing the irreducibility of nonsquare Perron-Frobenius systems

AU - Avin, C.

AU - Borokhovich, M.

AU - Haddad, Y.

AU - Kantor, E.

AU - Lotker, Z.

AU - Parter, Merav

AU - Peleg, David

PY - 2014/12

Y1 - 2014/12

N2 - The Perron-Frobenius (PF) theorem provides a simple characterization of the eigenvectors and eigenvalues of irreducible nonnegative square matrices. A generalization of the PF theorem to nonsquare matrices, which can be interpreted as representing systems with additional degrees of freedom, was recently presented in [1]. This generalized theorem requires a notion of irreducibility for nonsquare systems. A suitable definition, based on the property that every maximal square (legal) subsystem is irreducible, is provided in [1], and is shown to be necessary and sufficient for the generalized theorem to hold. This note shows that irreducibility of a nonsquare system can be tested in polynomial time. The analysis uses a graphic representation of the nonsquare system, termed the constraint graph, representing the flow of influence between the constraints of the system.

AB - The Perron-Frobenius (PF) theorem provides a simple characterization of the eigenvectors and eigenvalues of irreducible nonnegative square matrices. A generalization of the PF theorem to nonsquare matrices, which can be interpreted as representing systems with additional degrees of freedom, was recently presented in [1]. This generalized theorem requires a notion of irreducibility for nonsquare systems. A suitable definition, based on the property that every maximal square (legal) subsystem is irreducible, is provided in [1], and is shown to be necessary and sufficient for the generalized theorem to hold. This note shows that irreducibility of a nonsquare system can be tested in polynomial time. The analysis uses a graphic representation of the nonsquare system, termed the constraint graph, representing the flow of influence between the constraints of the system.

UR - http://www.scopus.com/inward/record.url?scp=84904274056&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2014.05.004

DO - 10.1016/j.ipl.2014.05.004

M3 - Article

SN - 0020-0190

VL - 114

SP - 728

EP - 733

JO - Information Processing Letters

JF - Information Processing Letters

IS - 12

ER -

Testing the irreducibility of nonsquare Perron-Frobenius systems

Abstract

Funding

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this