We prove the existence of $(-1,1)$-matrices with near-extremal properties. In particular, we find matrices having either small inner products between all pairs of distinct rows or having determinants approaching Hadamard's bound. Our approach is to study the $m \times n$ submatrices of a Hadamard matrix of order k. We use both the probabilistic method to obtain information about randomly selected submatrices and also combinatorial bounds which hold for all submatrices. Our existence results depend upon the gaps between successive primes. Beyond the applications presented in this paper, the study of randomly selected submatrices of combinatorial designs is of intrinsic interest.

We study two-dimensional (2-D) arrays of fourth roots of unity which have all out-of-phase periodic autocorrelations equal to zero. Generalizing the concept of a perfect binary array, we call these arrays perfect quaternary arrays. We establish connections with combinatorial design theory and exhibit large families of such arrays. Increasing the alphabet from size two to size four greatly increases the flexibility one has in choosing the dimensions for 2-D arrays with perfect periodic autocorrelation. For example, we show that the number of entries in a 2-D perfect quaternary array may be divisible by any Mersenne prime and indeed by many other primes, whereas 2-D perfect binary arrays are only known to exist with size equal to a power of two times a power of three.

Let A(n,d) denote the greatest number of codewords possible in a binary block code of length n and distance d. Plotkin gave a simple counting argument which leads to an upper bound B(n,d) for A(n,d) when d>n/2. Levenshtein (1964) proved that if Hadamard's conjecture is true then Plotkin's bound is sharp. Though Hadamard's conjecture is probably true, its resolution remains a difficult open question. So it is natural to ask what one can prove about the ratio R(n,d)=A(n,d)/B(n,d). This note presents an efficient heuristic for constructing, for any d/spl ges/n/2, a binary code which has at least 0.495B(n,d) codewords. A computer calculation confirms that R(n,d)>0.495 for d up to one trillion.

For the case where H(v,r,n) denotes an n-dimensional Hadamard matrix of order v whose r-dimensional sections are all r-dimensional Hadamard matrices, and where C(v,r,n) denotes the set of H(v,r,n), the author describes the connections between C(2/sup t/,r,n) and Reed-Muller codes. Let R(r,n) denote the rth-order Reed-Muller code of length 2/sup n/. It is shown that C(2,2,n) is a coset of R(1,n) and that C(2,r,n) is the union of cosets of R(1,n). The author shows that when r>or=3, C(2,r,n) is a subcode of R(r-1,n). Moreover, when s,t>or=1 and m>or=r>or=2, C(2/sup st/,r,m) is shown to be a subcode of C(2/sup s/,m(t-1)+r,mt). This allows one to determine the excesses of the proper H(2,2n,n)'s, to prove that the Hadamard transform can be used to repair a corrupted H(2,2,n) in order n2/sup n/ steps and that the usual methods for decoding Reed-Muller codes can be used to correct up to n2/sup n-r/-1 errors in any H(2,r,n).>