×

zbMATH — the first resource for mathematics

A problem on 0-1 matrices. (English) Zbl 0741.15007
Author’s summary: We compute the maximal and the minimal value of \(\| M^ 2\|\) over the class of \(0-1\) valued \(n\times n\) matrices \(M\) with \(k\) entries equal to one for fixed \(k\) and \(n\), where \(\|\centerdot\|\) denotes the sum of the entries. This result has applications to graph theory and probability theory.

MSC:
15B36 Matrices of integers
05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)
60G10 Stationary stochastic processes
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A60 Norms of matrices, numerical range, applications of functional analysis to matrix theory
Keywords:
0–1 matrices; norm
PDF BibTeX XML Cite
Full Text: Numdam EuDML
References:
[1] J. Aaronson and D. Gilat , On the structure of stationary one dependent processes , School of Mathematical Sciences, Tel Aviv Univ., Israel, (1987).
[2] J. Aaronson , D. Gilat , M.S. Keane and V. De Valk , An algebraic construction of a class of one-dependent processes , Annals of Probability 17 (1989) 128-143. · Zbl 0681.60038 · doi:10.1214/aop/1176991499
[3] L. Finke , Two maximization problems, a paper submitted to Oregon State Univ. in partial fulfillment of the requirements for the degree of Master of Arts , 1982.
[4] A. Gandolfi , M.S. Keane and V. De Valk , Extremal two-correlations of two-valued stationary one-dependent processes , accepted by Prob. Theory and Related Fields (1988). · Zbl 0638.60056 · doi:10.1007/BF01794435
[5] G.H. Hardy , J.E. Littlewood and G. Pólya , Inequalities , Cambridge Univ. Press (1934). · Zbl 0010.10703
[6] M. Katz , Rearrangements of (0,1) matrices, Israel Journ . of Mathematics, 9 (1971) 53-72. · Zbl 0215.33405 · doi:10.1007/BF02771620
[7] A. Khintchine , Über eine Ungleichung , Mat. Sb. 39 (1932) 35-39. · Zbl 0006.15803
[8] G.G. Lorentz , A problem of plane measure , Amer. Journ. Math. 71 (1949) 417-426. · Zbl 0032.19701 · doi:10.2307/2372255
[9] W.A.J. Luxemburg , On an inequality of A. Khintchine for zero-one matrices , Journ. of Combinatorial Theory 12 (1972) 289-296. · Zbl 0241.05017 · doi:10.1016/0097-3165(72)90043-X
[10] V. De Valk , The maximal and minimal 2-correlation of a class of 1-dependent 0-1 valued processes , Israel Journ. of Math. 62 (1988) 181-205. · Zbl 0661.60028 · doi:10.1007/BF02787121
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.