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.     

Some inequalities for multidimensional (0,1)- matrices

Can there exist a (0,1)-matrix of order n and dimension d, such that the sum on any e-dimensional hyperplane of the matrix is a fixed number r? The answer to this question is of importance both for the construction of incomplete block designs and for the investigation of extremal points in the convex sets of multidimensional stochastic matrices. Some necessary conditions that must be fulfilled by the parameters n, d, e, and r are deduced in this paper.     

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.     

A generalized solution in W2 1(0,1) of a problem concerning the deflection of a beam

A new method is proposed for formulating a boundary-value problem for a fourth-order ordinary differential equation with a solution in W₂ ¹(0, 1). This generalized formulation is based on a system of second-order equations with coefficients in W₂ ^–1 (0, 1). The existence and uniqueness of the indicated solution in this class is proven.Translated fromVychislitel'naya i Prikladnaya Matematika, No. 69, pp. 90–96, 1989.     

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.     

A maximum problem for matrices

The following maximum problem is considered: To find among all contractions T on an n-dimensional Hilbert space whose spectral radius does not exceed a given number p< 1, the operator T for which |Tⁿ| is maximum. A matrix T of Toeplitz type is constructed for which this maximum is attained.     

A problem on conjugacy of matrices

Let F be an infinite field and n?12. Then the number of conjugacy classes of the upper triangular nilpotent matrices in M_n(F) under action by the subgroup of GL_n(F) consisting of all the upper triangular matrices is infinite.     

The maximum,supremum, and spectrum for critical set sizes in (0,1)‐matrices

If is a partially filled‐in (0,1)‐matrix with a unique completion to a (0,1)‐matrix (with prescribed row and column sums), then we say that is a defining set for . A critical set is a minimal defining set (the deletion of any entry results in more than one completion). We give a new equivalent definition of critical sets in (0,1)‐matrices and apply this theory to , the set of (0,1)‐matrices of dimensions with uniform row and column sum . The smallest possible size for a defining set of a matrix in is [N. Cavenagh, J. Combin. Des. 21 (2013), pp. 253–266], and the infimum (the largest‐smallest defining set size for members of ) is known asymptotically [N. Cavenagh and R. Ramadurai, Linear Algebra Appl. 537 (2018), pp. 38–47]. We show that no critical set of size larger than exists in an element of and that there exists a critical set of size in an element of for each such that . We also bound the supremum (the smallest‐largest critical set size for members of ) between and .     

A Characterization of a Class of Symmetric(0,1)Matrices

ＡＣｈａｒａｃｔｅｒｉｚａｔｉｏｎｏｆａＣｌａｓｓｏｆＳｙｍｍｅｔｒｉｃ（０，１）ＭａｔｒｉｃｅｓＬｉＷｅｎ（黎稳）（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＳｏｕｔｈＣｈｉｎａＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｇｕａｎｚｈｏｎ，５１０６３１...     

A recipe for semidefinite relaxation for (0,1)-quadratic programming

We review various relaxations of (0,1)-quadratic programming problems. These include semidefinite programs, parametric trust region problems and concave quadratic maximization. All relaxations that we consider lead to efficiently solvable problems. The main contributions of the paper are the following. Using Lagrangian duality, we prove equivalence of the relaxations in a unified and simple way. Some of these equivalences have been known previously, but our approach leads to short and transparent proofs. Moreover we extend the approach to the case of equality constrained problems by taking the squared linear constraints into the objective function. We show how this technique can be applied to the Quadratic Assignment Problem, the Graph Partition Problem and the Max-Clique Problem. Finally we show our relaxation to be best possible among all quadratic majorants with zero trace.The research was partially supported by GAR 201/93/0519.Research support by Christian Doppler Laboratorium für Diskrete Optimierung.Research support by the National Science and Engineering Research Council Canada.     

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.     

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.