On the inverse M-matrix problem for (0,1)-matrices

A graph-theoretic approach is used to characterize (0,1)-matrices which are inverses of M-matrices. Our main results show that a (0,1)-matrix is an inverse of an M-matrix if and only if its graph induces a partial order on its set of vertices and does not contain a certain specific subgraph.     

Universal tilings and universal (0,1)-matrices

A periodic regular tiling of the plane by black and white squares is k-universal if it contains all possible k × k blocks of black and white tiles. There is a 4 × 4 periodic tiling that is 2-universal; this paper looks for the smallest 3-universal tiling and obtains a 64 × 32 periodic tiling that is 3-universal.Related to this is the following: a (0,1)-matrix is k-universal if every possible k × k (0,1)-matrix occurs as a submatrix. It is proved that, for k even, there is a k2^k/2 matrix that is k-universal and, for k odd, there is a (3k + 1)2^(k−3)/2 by (3k − 1)2^k−3/2 matrix that is k-universal.     

Reconstructing (0,1)-matrices from projections using integer programming

We study the problem of reconstructing (0,1)-matrices based on projections along a small number of directions. This discrete inverse problem is generally hard to solve for more than 3 projection directions. Building on previous work by the authors, we give a problem formulation with the objective of finding matrices with the maximal number of neighboring ones. A solution approach based on variable splitting and the use of subgradient optimization is given. Further, computational results are given for some structured instances. Optimal solutions are found for instances with up to 10,000 binary variables.     

The asymptotic number of (0,1)-matrices with zero permanent

It is shown that Z_n/n·2^{n2 - n + 1}→1, where Z_n is the number of n × n (0,1)-matrices with zero permanent.     

行和列和为常量的(0,1)-矩阵的计数

Let fs,t(m,n) be the number of (0,1) - matrices of size m x n such that each row has exactly s ones and each column has exactly t ones (sm = nt). How to determine fs,t(m,n)? As R. P. Stanley has observed (Enumerative CombinatoricsⅠ(1997), Example 1.1.3), the determination of fs,t(m, n) is an unsolved problem, except for very small s, t. In this paper the closed formulas for f2,2(n,n), f3,2(m,n), f4,2(m,n) are given. And recursion formulas and generating functions are discussed.     

The numerical range of certain 0,1-matrices

Let A be a 0, 1-matrix with at most one 1 in each row and column. The authors prove that the numerical range of A is the convex hull of a polygon and a circular disk, both centered at the origin and contained in the unit disk. The proof uses a permutation similarity to reduce A to a direct sum of matrices whose numerical ranges can be determined. A computer program, developed by the authors, which plots the boundary of the numerical range of an arbitrary complex matrix is also discussed.     

The 1-width of (0,1)-matrices having constant row sum 3

In this note we establish upper bounds for the 1-width of an m × n matrix of 0's and 1's having three 1's in every row and having a constant number, c, of 1's in every column. When c = 3, this upper bound is $\text{n}\text{2}$ and when c = 4 this estimate is $\text{5n}\text{9}$. In these cases the upper bound is best possible, in the sense that for every possible size there exist matrices with this maximal 1-width. The technique of proof is also used to improve the known bound for the 1-width of (0, 1)-matrices with constant line sum 4.     

(0,1)-矩阵的积和式的图表示及其相关性质

将(0，1)．矩阵的积和式的记数问题转化为它的伴随图或伴随有向图上相关元素的记数问题，能使复杂的计数问题变得相对直观化和简单化．本文给出了(0，1)-矩阵的积和式的图论表达式，并以该表达式为基础，主要解决了2．正则图类的邻接矩阵的最大积和式的记数问题以及它的反问题，即确定了零积和式临界图的极大边数及其图类．     

On (0,1)-matrix semigroups

In this paper we count the number of elements and idempotents in certainD-classes of the semigroup B_n of all binary relations on a set of n elements, namely whose those row and column rank do not exceed 3. This is an announcement of the results; detailed proofs of all results are contained in [2]. The author presented the abstract of this paper in person at Tacoma, Washington, the 676 Meeting of the Amer. Math. Soc., June 20, 1970.     

On the discrepancy of (0,1)-sequences

We give bounds for the L^p-discrepancy, , of the van der Corput sequence in base 2. Further, we give a best possible upper bound for the star discrepancy of (0,1)-sequences and show that this bound is attained for the van der Corput sequence. Finally, we give a (0,1)-sequence with essentially smaller star discrepancy than for the van der Corput sequence.     

On the joint spectral radius of matrices of order 2 with equal spectral radius

We provide explicit formulas for the joint spectral radius of certain classes of pairs of real matrices of order 2 with equal spectral radius.     

On convertible (0,1) matrices

A square matrix A with per A≠0 is called convertible if there exists a (1, -1) matrix H such that per A=det(H o A) where H o A denote the Hadamard product of H and A In this paper, an upper bound of permanents of maximal convertible (0,1) matrices A with π(A)≥4(n-1) is obtained.     

On the distance spectral radius of cacti

A cactus is a connected graph in which any two cycles have at most one common vertex. In this article, we determine the unique graph with minimal distance spectral radius in the class of all cacti with n vertices and k cycles. Also, we determine the unique graph with minimal distance spectral radius in the class of all cacti with n vertices and r pendent vertices. Moreover, we determine the class of cacti in which the maximal distance spectral radius among all cacti with n vertices and k cycles is attained.     

On the spectral radius of functional operators

An estimate of the spectral radius of functional operators generated by operators of multiplication and shift operators in the space of continuous vector functions on the interval is given. It is assumed that shifts have fixed points only at both ends of the interval and belong to one type, i.e., they are either left or right shifts.     

Quotient of spectral radius, (signless) Laplacian spectral radius and clique number of graphs

In this paper, the upper and lower bounds for the quotient of spectral radius (Laplacian spectral radius, signless Laplacian spectral radius) and the clique number together with the corresponding extremal graphs in the class of connected graphs with n vertices and clique number ω(2 ≤ ω ≤ n) are determined. As a consequence of our results, two conjectures given in Aouchiche (2006) and Hansen (2010) are proved.