MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A complex $n\times n$ matrix $A=[a_{ij}]$ is called a Hadamard matrix if $A^{+}A=nI$ and $|a_{ij}|=1$ holds for all $i,j$, where $A^{+}$ denotes the conjugate transposed matrix of $A$, and a vector $x=(x_1,x_2.....x_n)\in C^n$ is called unit if $|x_i|=1$ holds for all $i$.

For $n>5$, are there $d\times n$ matrix $F=[f_{ij}]$ which satisfies the following properties:

1) $FF^{+}=dI$,

2) $|f_{ij}|=1$ , holds for all $i,j$,

3) there is no unit vector $x\in C^n$ satisfies $F x^{+}=0$.

Which can be regarded as the difficulty of generate complex Hadamard Matrix, actually, it is wanted to show the following method to find a complex Hadamard Matrix does not always work:

Let $S$ be an empty set, choose a unit vector $x$ which is orthogonal to all the elements in $S$, and put $x$ in $S$, until there is no unit vector which orthogonal to all elements in $S$. Now what we ask can be regarded as is it possible that the algorithm stops but $|S|< n$.

share|cite|improve this question
What, exactly, is the question? – Harald Hanche-Olsen Nov 5 '10 at 6:17
My take: are there dxn matrices which look like submatrices of an nxn complex Hadamard matrix, but actually are not? Gerhard "Ask Me About System Design" Paseman, 2010.11.04 – Gerhard Paseman Nov 5 '10 at 6:32
Exactly as what you said. – gondolf Nov 5 '10 at 6:34
Despite Gerhard's best efforts, I still don't understand what's being asked. Perhaps it's time for MO to hire a full-time mindreader, fluent in mathematics. – Gerry Myerson Nov 5 '10 at 10:37
The latest edit is helpful, but I wonder whether in condition 3 you really only want $x$ to be a unit vector, which just means a vector of length 1. In the previous edit, you asked for all the components of $x$ to have modulus 1, a very different thing. The way you have it now, I think it's trivial that there is no such $F$. – Gerry Myerson Nov 5 '10 at 13:15

what happens exactly for n=5 ???

share|cite|improve this answer
The OP opinion will be welcomed here to have a chance to really understand what we want... – Luis H Gallardo Feb 15 '11 at 7:44
For $n=5$, such $3×5$ matrix F does exist! – gondolf Aug 9 '11 at 12:08

The circulant matrix $G$ with $3$ rows, $8$ columns and with first row

\begin{equation*} G= \begin{bmatrix} -1 & -1 & 1 & -1 & 1 & 1 & 1 & 1\\ \end{bmatrix} \end{equation*} satisfies

(1) $$ GG^{T} = 8I, $$


All entries in $G$ are $-1$ or $1$,


The only solution to: $XG=0$ is $X=0.$

Thus, there is no unit vector with $XG=0.$

share|cite|improve this answer
I am suspicious of the claim XG = 0. However, even if it holds, the problem is to show that one cannot find a complex unit vector X in C^8 with GX = 0. Given the degree of freedom in such a system, I suspect X exists. Gerhard "Ask Me About System Design" Paseman, 2011.01.17 – Gerhard Paseman Jan 17 '11 at 22:52
excuse me, I need to clarify: I am suspicious of the claim XG =0 implies X = 0. Gerhard "Know What Your Suspicions Are" Paseman, 2011.01.17 – Gerhard Paseman Jan 17 '11 at 22:54
Just do the computation ! Observe that we have only $3$ unknowns here (say $x,y,z$ ), we get quickly $x=0,y=0,z=0.$ – Luis H Gallardo Jan 18 '11 at 0:14
$X$ is assumed above to be a matrix with $1$ line and $3$ columns only. – Luis H Gallardo Jan 18 '11 at 0:19
Doesn't the OP really want that the only solution to $Gx=0$ is $x=0$, where $x$ is a vector with all unit entries? Matrices don't commute. – Peter Shor Feb 14 '11 at 23:41

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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