Binary matrices

---

Binary matrices

     

Parity check matrices and product representations of squares

Let \(N_{\mathbb{F}} \)(n,k,r) denote the maximum number of columns in an n-row matrix with entries in a finite field \(\mathbb{F}\) in which each column has at most r nonzero entries and every k columns are linearly independent over \(\mathbb{F}\). We obtain near-optimal upper bounds for \(N_{\mathbb{F}} \)(n,k,r) in the case k > r. Namely, we show that \(N_\mathbb{F} (n,k,r) \ll n^{\frac{r}{2} + \frac{{cr}}{k}} \) where \(c \approx \frac{4}{3}\) for large k. Our method is based on a novel reduction of the problem to the extremal problem for cycles in graphs, and yields a fast algorithm for finding short linear dependencies. We present additional applications of this method to a problem on hypergraphs and a problem in combinatorial number theory.     

Scattering matrices and Weyl functions

For a scattering system {A, A₀} consisting of self-adjoint extensionsA and A₀ of a symmetric operator A with finite deficiency indices,the scattering matrix {S()} and a spectral shift function arecalculated in terms of the Weyl function associated with a boundarytriplet for A*, and a simple proof of the Krein–Birmanformula is given. The results are applied to singular Sturm–Liouvilleoperators with scalar and matrix potentials, to Dirac operatorsand to Schrödinger operators with point interactions.     

Binary positive semidefinite matrices and associated integer polytopes

We consider the positive semidefinite (psd) matrices with binary entries, along with the corresponding integer polytopes. We begin by establishing some basic properties of these matrices and polytopes. Then, we show that several families of integer polytopes in the literature—the cut, boolean quadric, multicut and clique partitioning polytopes—are faces of binary psd polytopes. Finally, we present some implications of these polyhedral relationships. In particular, we answer an open question in the literature on the max-cut problem, by showing that the rounded psd inequalities define a polytope.     

Probability set functions

A probability set function is interpretable as a probability distribution on binary sequences of fixed length. Cumulants of probability set functions enjoy particularly simple properties which make them more manageable than cumulants of general random variables. We derive some identities satisfied by cumulants of probability set functions which we believe to be new. Probability set functions may be expanded in terms of their cumulants. We derive an expansion which allows the construction of examples of probability set functions whose cumulants are arbitrary, restricted only by their absolute values. It is known that this phenomenon cannot occur for continuous probability distributions. Some particular examples of probability set functions are considered, and their cumulants are computed, leading to a conjecture on the upper bound of the values of cumulants. Moments of probability set functions determined by arithmetical conditions are computed in a final example.Dedicated to our friend, W.A. Beyer. Financial support for this work was derived from the U.S.D.O.E. Human Genome Project, through the Center for Human Genome Studies at Los Alamos National Laboratory, and also through the Center for Nonlinear Studies, Los Alamos National Laboratory, LANL report LAUR-97-323.     

Binary quadratic and cubic forms,and unipositive matrices

The classical method of reducing a positive binary quadratic form to a semi-reduced form applies translations alternately left and right to minimize the absolute value of the middle coefficient — and may therefore be called absolute reduction. There is an alternative method which keeps the sign of the middle coefficient constant before the end: we call this method positive reduction. Positive reduction seems to make possible an algorithm for finding the representations of 1 by a binary cubic form with real linear factors, and has various properties somewhat simpler than those of absolute reduction. Some of these properties involve unipositive matrices (with nonnegative integer elements and determinant 1). Certain semigroups of unipositive matrices with unique factorization into primes are described. Two of these semigroups give a neat approach to the reduction of indefinite binary quadratic forms—which may generalize. Some remarks on unimodular automorphs occur in Section 6.     

On the parity of generalized partition functions II

Let A = {а 1 < a 2 < ...} be a set of positive integers and A(x) its counting function. Let us denote the number of partitions of n with parts in A by p( A , n). Improving on two preceding papers jointly written with I.Z. Ruzsa and A. Sárközy (J. Number Theory, 1998) and with A. Sárközy (Millennial Conference on Number Theory, May 2000, Urbana, Illinois, U.S.A.), it is shown that there exists a set A satisfying A(x) > c xlog log x/ (log x) 1/3 , c<0, such that, for n large enough, p( A ; n) isalways even.     

Regular unbounded set functions

Set functions which are unbounded on an algebra of sets arise naturally by taking the products of bounded operators and spectral measures acting on a space of square integrable functions. The purpose of this note is to show that, provided a certain regularity condition is satisfied, there is a natural integration structure associated with such a set function and an auxiliary measure, so providing a complete space of integrable functions. Several examples illustrate the extent and limitations of the approach.     

Toeplitz matrices and classical and q-Bessel functions

We use biinfinite Toeplitz matrix analogues of classical and q-binomial identities in a commutative Banach algebra setting to characterize classical and q-Bessel functions of integer order and to establish properties of these functions.     

Learning read once functions using subcube parity queries

The article considers the problem of constructing a conditional diagnostic test (the exact identification problem) on the set of all read-once functions essentially dependent on the specified variables in an arbitrary hereditary basis. We use standard queries on function values at points and also parity queries on the number of ones in subfunctions obtained by substituting constants for variables (subcube parity queries return the modulo-2 sum of the function values on a subcube of the Boolean cube). For the elementary basis consisting of conjunction, disjunction, and negation, we prove the existence of a conditional diagnostic test with a quadratic (in the number of variables) number of queries. For bases that allow read-once expression of all elementary-basis functions (containing at least one nonmonotone and at least one nonlinear function) and are essentially different from the elementary basis, we prove the necessity of using an exponential (in the number of variables) number of queries in the worst case. Our analysis thus establishes the boundary between polynomial and exponential complexity problems.     

On functions of companion matrices

Presented in this paper are some new properties of a function f(C) of a companion matrix C, including (1) a representation of any entry of f(C) as a divided difference of f(λ) times a polynomial, (2) a similarity decomposition of f(C) generalizing that based on the Jordan form of C, and (3) characterization (construction) of all matrices that transform f(C) (by similarity) to companion form. The connection between functions of general and companion matrices is also dealt with, and a pair of dual relations is established.     

On compositive functions of matrices

Annali di Matematica Pura ed Applicata (1923 -) -     

Spectral set functions and scalar operators

A systematic study is made of continuous linear operators approximable (in certain topologies) by linear combinations of projections from the range of a spectral set function. Such operators may be viewed as natural analogues of the scalar-type spectral operators introduced by N. Dunford. We extend the classical theory so that the range of the spectral set function, necessarily a Boolean algebra of continuous projection operators, need not be uniformly bounded; it is this feature which gives the theory its wider range of applicability. Typically, the associated operational calculus, which is specified via a suitable integration process, is no longer related to a continuous homomorphism but merely to a certain kind of sequentially closed homomorphism.