Anti-Hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs (Q1369687)

The spectral norm of real matrix \(A\) is defined by \(|A|_s=\sup_{x\neq 0}|Ax|/|x|\), and if \(A\) is invertible then \(c(A)=|A|_s|A^-|_s\) is a condition number. This quantity measures are the sensibility of the equation \(Ax=b\) when the right hand side is changed. If \(c(A)\) is large, then \(A\) is called ill-conditioned. In this paper are investigated the most ill-conditioned \((0,1)\) (or \((-1,1)\)) matrices called anti-Hadamard matrices. Let \(A\) be a non-singular \((0,1)\)-matrix and \(B=A^{-1}=(b_{i,j}).\) Denote \[ \chi (A)=\max_{i,j}|b_{i,j}|\qquad \text{and}\qquad \chi(n)=\max_A\chi(A), \] \[ \mu (A)=\sum_{i,j} b_{i,j}^2 \qquad \text{and} \qquad \mu (n)=\max_A\mu (A). \] A real function \(f\) is called super-multiplicative when \(f(m+n)\geq f(m)f(n)\) for all admissible \(m,n.\) \(A_n^1\) and \(A_n^2\) denote the sets of invertible \((0,1)\) and \((-1,+1)\)-matrices of order \(n\). Define \(\chi_i(n)=\max_{A\in A_n^i} \chi (A)\) for \(i=1,2\). The main result is the following theorem: (1) For \(i=1\) and 2, the functions \(\chi_i(n)\) are super-multiplicative and satisfy \[ 2^{(1/2)n\log n -n(1+o(1))}\geq \chi_i(n)\geq 2^{(1/2)n\log n -n(2+o(1))}. \] (2) One can construct explicitly a matrix \(C^i\in A_n^i \) such that \[ \chi(C^i)\geq 2^{(1/2)n\log n -n(2+o(1))}, \] where the \(o(1)\) term tends to 0 as \(n\) tends to infinity. Also some applications, as well as the estimation of the maximum possible norms of inverses of \((0,1)\) and \((-1,1)\)-matrices of order \(n\), and threshold gates with large weights are considered.