Skip to Main Content

Proceedings of the American Mathematical Society

Published by the American Mathematical Society since 1950, Proceedings of the American Mathematical Society is devoted to shorter research articles in all areas of pure and applied mathematics.

ISSN 1088-6826 (online) ISSN 0002-9939 (print)

The 2020 MCQ for Proceedings of the American Mathematical Society is 0.85.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Maximum rank of powers of a matrix of a given pattern
HTML articles powered by AMS MathViewer

by Svatopluk Poljak PDF
Proc. Amer. Math. Soc. 106 (1989), 1137-1144 Request permission

Abstract:

The pattern of a matrix is the structure of its zero and nonzero entries. For any prescribed pattern we determine the maximum possible rank of each power of a matrix with a given pattern. The approach is based on a combinatorial result that may be of some interest independently.
References
  • Claude Berge, Graphs and hypergraphs, North-Holland Mathematical Library, Vol. 6, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1973. Translated from the French by Edward Minieka. MR 0357172
  • Jack Edmonds, Systems of distinct representatives and linear algebra, J. Res. Nat. Bur. Standards Sect. B 71B (1967), 241–245. MR 229540
  • A. J. Hoffman, The role of unimodularity in applying linear inequalities to combinatorial theorems, Ann. Discrete Math. 4 (1979), 73–84. Discrete optimization (Proc. Adv. Res. Inst. Discrete Optimization and Systems Appl., Banff, Alta., 1977), I. MR 558555
    • J. Holenda and M. Schlegel, lecture presented at Czechoslovak Conference on Combinatorics, 1987.
  • John E. Hopcroft and Richard M. Karp, An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs, SIAM J. Comput. 2 (1973), 225–231. MR 337699, DOI 10.1137/0202019
    • S. Poljak, An announcement, Comm. Math. Univ. Car. 29, 1 (1988).
  • Alexander Schrijver, Theory of linear and integer programming, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Ltd., Chichester, 1986. A Wiley-Interscience Publication. MR 874114
  • Doron Zeilberger, A combinatorial approach to matrix algebra, Discrete Math. 56 (1985), no. 1, 61–72. MR 808086, DOI 10.1016/0012-365X(85)90192-X
Similar Articles
  • Retrieve articles in Proceedings of the American Mathematical Society with MSC: 15A03, 05C20, 05C38
  • Retrieve articles in all journals with MSC: 15A03, 05C20, 05C38
Additional Information
  • © Copyright 1989 American Mathematical Society
  • Journal: Proc. Amer. Math. Soc. 106 (1989), 1137-1144
  • MSC: Primary 15A03; Secondary 05C20, 05C38
  • DOI: https://doi.org/10.1090/S0002-9939-1989-0963575-5
  • MathSciNet review: 963575