A graph theoretic approach to matrix inversion by partitioning
dc.contributor.author | Harary, Frank | en_US |
dc.date.accessioned | 2006-09-11T17:38:14Z | |
dc.date.available | 2006-09-11T17:38:14Z | |
dc.date.issued | 1962-12 | en_US |
dc.identifier.citation | Harary, Frank; (1962). "A graph theoretic approach to matrix inversion by partitioning." Numerische Mathematik 4(1): 128-135. <http://hdl.handle.net/2027.42/46321> | en_US |
dc.identifier.issn | 0029-599X | en_US |
dc.identifier.issn | 0945-3245 | en_US |
dc.identifier.uri | https://hdl.handle.net/2027.42/46321 | |
dc.description.abstract | Let M be a square matrix whose entries are in some field. Our object is to find a permutation matrix P such that PM P −1 is completely reduced, i.e., is partitioned in block triangular form, so that all submatrices below its diagonal are 0 and all diagonal submatrices are square and irreducible. Let A be the binary (0, 1) matrix obtained from M by preserving the 0's of M and replacing the nonzero entries of M by 1's. Then A may be regarded as the adjacency matrix of a directed graph D . Call D strongly connected or strong if any two points of D are mutually reachable by directed paths. A strong component of D is a maximal strong subgraph. The condensation D * of D is that digraph whose points are the strong components of D and whose lines are induced by those of D . By known methods, we construct D * from the digraph, D whose adjacency matrix A was obtained from the original matrix M . Let A * be the adjacency matrix of D * . It is easy to show that there exists a permutation matrix Q such that QA * Q −1 is an upper triangular matrix. The determination of an appropriate permutation matrix P from this matrix Q is straightforward. | en_US |
dc.format.extent | 378865 bytes | |
dc.format.extent | 3115 bytes | |
dc.format.mimetype | application/pdf | |
dc.format.mimetype | text/plain | |
dc.language.iso | en_US | |
dc.publisher | Springer-Verlag | en_US |
dc.subject.other | Appl.Mathematics/Computational Methods of Engineering | en_US |
dc.subject.other | Mathematics | en_US |
dc.subject.other | Numerical Analysis | en_US |
dc.subject.other | Mathematical Methods in Physics | en_US |
dc.subject.other | Mathematics, General | en_US |
dc.subject.other | Mathematical and Computational Physics | en_US |
dc.subject.other | Numerical and Computational Methods | en_US |
dc.title | A graph theoretic approach to matrix inversion by partitioning | en_US |
dc.type | Article | en_US |
dc.subject.hlbsecondlevel | Mathematics | en_US |
dc.subject.hlbtoplevel | Science | en_US |
dc.description.peerreviewed | Peer Reviewed | en_US |
dc.contributor.affiliationum | Mathematics Department, The University of Michigan, Ann Arbor, Michigan | en_US |
dc.contributor.affiliationumcampus | Ann Arbor | en_US |
dc.description.bitstreamurl | http://deepblue.lib.umich.edu/bitstream/2027.42/46321/1/211_2005_Article_BF01386304.pdf | en_US |
dc.identifier.doi | http://dx.doi.org/10.1007/BF01386304 | en_US |
dc.identifier.source | Numerische Mathematik | en_US |
dc.owningcollname | Interdisciplinary and Peer-Reviewed |
Files in this item
-
Interdisciplinary and Peer-Reviewed
-
Mathematical Geography, Institute of (IMaGe)
Publications and Scholarly Research Projects.
Remediation of Harmful Language
The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.
Accessibility
If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.