Low Rank Matrices with a Given Sign Pattern
P. Delsarte, Yves Kamp · SIAM Journal on Discrete Mathematics · 1989
Given an $m \times n$ sign matrix S, an $m \times n$ real matrix A is said to be a realization of S if the sign of the $(i,j)$-entry of A equals the $(i,j)$-entry of S. This paper deals with the problem of finding low rank realization matrices A. It is motivated by a minimization problem in multilayer perceptrons. The subject is approached by means of the Farkas lemma, which allows characterization of the sign matrices realizable with a given rank. Based on this result and on some other standard techniques of matrix algebra such as the cyclic Fourier transform, low rank realizations are obtained for sign matrices having certain nice combinatorial structures. Furthermore, the paper includes an elementary lower bound on the rank and a counting of realizable sign vectors.