# Existence or construction of a sequence of orthogonal matrices with three properties

This is a problem that I encountered during my research, and I have spent a good amount of time on it without success. So I am reaching out for help .... Any pointers or suggestions are appreicated!

The problem: Let $m\geq8$ be an even integer and $\varepsilon,\alpha\in\left( 0,1\right)$ be two fixed constants. For each $m$ large enough, construct or an orthogonal matrix $\mathbf{T}_{m}=\left( \gamma_{ij}\right)$ such that

1. Each $\gamma_{ij} \neq 0$ for $1 \leq i \leq j \leq m$;

2. The following inequality holds $$1 -\varepsilon \geq \min_{\left[ \alpha m\right] +1\leq i\leq m}\sum_{j=\left[ \alpha m\right] +1}^{m}\gamma_{ij}^{2}\geq\varepsilon,$$ where $\left[ x\right]$ denotes the integer part of $x\in\mathbb{R}$.

1. Put the last $m-[\alpha m]$ columns (by keeping the order of the column indices) of $\mathbf{T}_{m}$ into a matrix $\mathbf{R}$. Then, for the matrix $\mathbf{R}$ and a constant $\beta \in (0,\alpha)$, pick a submatrix $\mathbf{G}$ of size $[\beta m] \times (m-[\alpha m])$ from the first $[\alpha m]$ rows of $\mathbf{R}$. Also pick a submatrix of $\mathbf{H}$ of size $[\beta m] \times (m-[\alpha m])$ from the last $m-[\alpha m]$ rows of $\mathbf{R}$. Then, no such $\beta$ exists such that $\mathbf{G} = - \mathbf{H}$ or $\mathbf{G} = \mathbf{H}$ for any $\mathbf{G}$ and $\mathbf{H}$ thus picked.

The inequality in display requires that the lower right block of size $[\left( 1-\alpha\right) m]$ of $\mathbf{T}_{m}$ has rows of Euclidean norms bounded from below by $\varepsilon$ and from above by $1 -\varepsilon$ regardless of what $m$ is. It becomes highly nontrivial to obtain such a $\mathbf{T}_{m}$.

Constructive proof for such a sequence $\left\{ \mathbf{T}_{m}\right\} _{m\geq8,m\in2\mathbb{N}}$ is preferred.

Note I edited the problem. Now a third restriction is added. Without the third restriction, Walsh matrices pointed by Dr. Bill Johnson satisfy the rest two.

Background I encountered this problem when I was trying to contruct a counterexample to a general claim made in a published paper on the convergence of a stochastic process related to high-dimensional multiple testing.

My attempts The simple reflection trick to construct an orthogonal matrix is not able to obtain $\mathbf{T}_m$ for which the displayed inequality holds. I also tried (a) using the Haar measure to show the existence of such an $\mathbf{T}_m$ with positive probability but it essentially reduces to the same problem described above; (b) tried orthogonal matrix induced by dicrete cosine transform, but it can not achieve the uniformity needed in the displayed inequality.

• Use Walsh matrices. – Bill Johnson Dec 6 '15 at 19:14
• @Stefan Kohl: how to add a top-level tag?@Bill Johnson: I see; only need to normalize the Walsh matrices. Thank you both! – Chee Dec 6 '15 at 19:59
• Probably you don't mean what you wrote down as a formula (your verbal description doesn't match this either). To get the minimum between the required bounds, just take a lower right block that is diagonal, with all $1$'s, except for one $\sqrt{\epsilon}$, and now it's trivial to build a unitary matrix out of this (it can be diagonal except for two non-diagonal entries). – Christian Remling Dec 6 '15 at 21:19
• @ChristianRemling: sharp eyes! After I posted the orignal problem, where it was also required that $\gamma_{ij} \neq 0$ for each $i,j$, I removed this requirement since I thought it may be hard to find such an orthogonal matrix for each such $m$. Then Dr. Johnson pionted out the Walsh matrices, which satisfy both two requirements. Now that I have read your comments, and I added this requirement back. – Chee Dec 7 '15 at 1:04
• @Chee: I don't think requiring $\gamma_{ij}\not= 0$ changes much, I'm pretty confident a small perturbation (within $O(m)$) of my example (say) will have this property generically. – Christian Remling Dec 7 '15 at 20:17