# The difficulty of generate complex Hadamard Matrix

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$.

• 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

## 2 Answers

what happens exactly for n=5 ???

• 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,$$

(2)

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

(3)

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

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

• 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