Sparsity of orthogonal matrices with restrictions
type: Item
instance of: scholarly article
title: Sparsity of orthogonal matrices with restrictions
zbMATH Open document ID: 0952.15014
DOI: 10.1016/S0024-3795(99)00233-5
author: Gi-Sang Cheon
author: Bryan L. Shader
published in: Linear Algebra and its Applications
publication date: 2001-01-15T00:00:00Z
review text: The authors study the sparsity of orthogonal matrices that have a fixed number, \(k>0\), of full columns. In particular, Corollary 4.2 asserts that minimum number of nonzero entries in an \(m\times m\) orthogonal matrix with \(k\) full columns is \[ \left(\left[ \lg{m\over k}\right] +k+2\right) m-k 2^{\bigl [\lg(m/k) \bigr ]+1}. \] In order to prove Corollary 4.2, they prove something stronger. A matrix is row-orthogonal provided each of its rows is nonzero and its rows are pairwise orthogonal. Corollary 4.1 asserts that the minimum number of nonzero entries in an \(m\times n\) row-orthogonal matrix with \(k\) full columns and no column of zeros is \[ \left(\left[ \lg\left({m\over k}\right) \right]+ k+2 \right) m-k 2^{\bigl[\lg(m/k) \bigr]+1}+(n-m). \] A consequence of this result is that if \(A\) is an \(m\times n\) row-orthogonal matrix with \(n>m\), with no column of zeros and \[ \#(A)<\left( \left[\lg\left( {n\over n-m}\right) \right]+ 2\right) n-(n-m) 2^{\bigl[ \lg(n/n-m) \bigr]+1}, \] then each vector orthogonal to the rows of \(A\) has an entry equal to 0. Also, for integers \(k\) and \(n\) with \(k\leq n\), the minimum number of nonzero entries is \(n\times n\). A connected, orthogonal matrix having a column with at least \(k\) nonzero entries is determined.
Mathematics Subject Classification ID: 15B57
zbMATH DE Number: 1421383
zbMATH Keywords: sparse matrices
zbMATH Keywords: orthogonal matrices
reviewed by: Yueh-er Kuo
MaRDI profile type: Publication
cites work: Q4281318
cites work: How sparse can a matrix with orthogonal rows be?
cites work: Sparse orthogonal matrices and the Haar wavelet
cites work: Combinatorially orthogonal matrices and related graphs
cites work: A simple proof of Fiedler's conjecture concerning orthogonal matrices
cites work: Sign pattern matrices that allow orthogonality
description: scientific article; zbMATH DE number 1421383