6
$\begingroup$

I came across the following conjecture, reading a recent paper in the Monthly, an orthogonal matrix of order $n\neq 0 \pmod 4$ has a nonnegative (up to a scalar) row vector. It should be straight in dimensions $2$ and $3$.

$\endgroup$

closed as unclear what you're asking by Alexandre Eremenko, Ben McKay, Joonas Ilmavirta, user44191, Chris Godsil Jul 20 at 13:04

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ presumably with "raw vector" you refer to a row of the matrix? are you asking for a proof? $\endgroup$ – Carlo Beenakker Jul 19 at 6:08
  • 2
    $\begingroup$ I do not understand the last sentence. $\endgroup$ – Alexandre Eremenko Jul 19 at 6:10
  • $\begingroup$ yup row=raw thanks, if there is a proof that would be more than expected $\endgroup$ – Toni Mhax Jul 19 at 6:46
  • 1
    $\begingroup$ By non-negative you mean that all entries are non-negative? And orthogonal should be over the reals? $\endgroup$ – Dirk Jul 19 at 6:57
  • $\begingroup$ yes they are of the same sign $\endgroup$ – Toni Mhax Jul 19 at 6:59
13
$\begingroup$

This is false already for $n=3$. A counterexample is given by the matrix

$$A=\frac{1}{3}\begin{bmatrix} 2 & 2 & -1\\ 2 & -1 & 2\\ -1& 2 & 2 \end{bmatrix}. $$

How did I construct this matrix? Start with $(a,b,c)$ such that $ab+bc+ca=0$, where $a,b,c\ne 0$. Observe that $a,b,c$ cannot be of the same sign. Renormalize it to be of unit length, consider the corresponding (anti-)circulant matrix $A$ and VOILA! Solving the equation is easy: $\displaystyle c=-\frac{ab}{a+b}.$

More generally, for any $n\geq 3$, consider a real unit row-vector ${\bf a}=(a_1,\ldots,a_n)$ such that all entries are non-zero and ${\bf a}$ is orthogonal to its cyclic permutations, i.e. $a_{i}\ne 0,\, \sum_{i=1}^n a_{i}^2=1$ and $$\displaystyle\sum_{i=1}^n a_{i}a_{i+p}=0{\ \ }{\rm for}{\ }1\leq p\leq n-1,\tag {*}$$ where $a_{j+n}=a_{j}.\ $ Then the matrix $A$ whose rows are successive cyclic permutations of the row vector ${\bf a}$ is orthogonal with non-zero entries, but has no row with entries of the same sign. To construct such a vector, one only needs to solve a system of $\displaystyle m=\lfloor\frac{n}{2}\rfloor$ homogeneous quadratic equations (*) with $1\leq p\leq m$ in non-zero reals and renormalize the solution to be a unit vector. This is straightforward, but the hour is late, so let me leave it as an exercise to the interested readers.

$\endgroup$
  • $\begingroup$ I couldn't find a counterexemple to my conjecture. $\endgroup$ – Toni Mhax Jul 19 at 8:51
  • $\begingroup$ Thinking of an orthogonal matrix geometrically in terms of the orthogonal basis formed by its rows immediately convinced me that the conjecture is unreasonable beyond the case $n=2$, where there is too little room. The rest is a matter of perseverance or solid linear algebra technique, depending on one's background. $\endgroup$ – Victor Protsak Jul 19 at 8:57
12
$\begingroup$

Here's a simple argument that this is false for $n > 2$.

In dimension $n$ there are $2^{n}$ orthants, $2^{n-1}$ if one considers them modulo sign. A pair of antipodal orthants means a pair of orthants whose sign patterns are exactly opposite (e.g. the positive orthant union the negative orthant).

The key point is that an orthonormal frame contains $n$ vectors, no two of which lie in the same pair of antipodal orthants. If two nonzero vectors lie in the interior of the same orthant, then their inner product is positive because it is a sum of nonnegative numbers not all of which are zero. (If they lie on the boundary of the same orthant, a small rotation moves them to different orthants).

The original "conjecture" supposes that necessarily one of the vectors of an orthonormal frame lies in a particular orthant. However, since $2^{n-1} > n$ if $n > 2$, necessarily some pair of antipodal orthants contains no vector of the frame (pigeonhole principle). Since permutations of the coordinates are orthogonal transformations permuting the orthants (and preserving antipodal orthants), given a particular orthant there is always an orthonormal frame containing no vector of the orthant.

(Note that the preceding is a bit vague in that it is not specified whether orthants are open or closed; since the goal is to build a counterexample, this does not matter much.)

$\endgroup$
  • 3
    $\begingroup$ This is a nice argument! You just need to be careful with the walls: it is possible for two orthogonal vectors to lie on the boundary of the same orthant (or antipodal pair); this happens for the standard basis, where each basis vector is in the closure of every antipodal pair of orthants. $\endgroup$ – Victor Protsak Jul 19 at 10:46
  • $\begingroup$ @VictorProtsak: edited to take into account your remark. $\endgroup$ – Dan Fox Jul 19 at 11:00
  • $\begingroup$ This argument is fantastic! This really quantifies the notion of 'enough room' in Victor's comment to his answer. $\endgroup$ – Steven Stadnicki Jul 19 at 20:49
4
$\begingroup$

Not an answer, just an extended comment.

The conjecture is true for $n=2$ since we know the shape of orthogonal matrices: $\begin{pmatrix}a & -b \cr b & a\end{pmatrix}$ or $\begin{pmatrix}a & b \cr b & -a\end{pmatrix}$ for some $a,b\in\mathbb{R}$ such that $a^2+b^2=1$.

For $n=4,$ there are counterexamples, such as$ M=\dfrac{1}{2}\begin{pmatrix} -1 & 1 & -1 & 1 \\ -1 & -1 & 1 & 1 \\ 1 & -1 & -1 & 1 \\ -1 & -1 & -1 & -1 \end{pmatrix}$ Taking block diagonal matrices whose diagonal blocks are all equal to $M$ yield a counterexample for any $n\equiv 0 \ [4]$, so we cannot expect a better result than the one which is conjectured.

Notice now that transposition induces a bijection on the set of orthogonal matrices, so we can safely replace "row" by column".

Therefore, the conjecture may be rephrased as: for $n\not\equiv 0 \ [4]$, any orthonormal basis of $\mathbb{R}^n$ contains a vector whose coordinates all have the same sign.

Assume that $n=3$, and let $(u,v,w)$ be an orthonormal basis. Exchanging $u,v$ if necessary, one may assume that this basis is direct, so $w=u\wedge v$. Note that the answer is not affected by multiplication of $u$ or $v$ by a scalar, so what we really have to prove is: assume that $u,v$ are orthogonal and that the coordinates of $u$ (resp. $v$) do not have the same sign, then the coordinates of $u\wedge v$ have the same sign. This should be easy (but tedious) to check. (I have not tried yet)

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.