HW4

1. Construct a Hadamard matrix of order 28 using Williamson’s method.

• $A_1^2+A_2^2+A_3^2+A_4^2=4n{I}_n$.

Link to original

Consider $\vec{j}=(1,1,\cdots ,1{)}^T$. Assume that $s_i$ is the sum of the first row of $A_i$, then $(A_1^2+\cdots +A_4^2)\vec{j}=(s_1^2+\cdots +s_4^2)\vec{j}=28\vec{j}$. Notice that

& 1^2+1^2+1^2+5^2=1+1+1+25=28 \\ & 2^2+2^2+2^2+4^2=28 \\ & 3^2+3^2+3^2+1^2=9+9+9+1=28 \end{aligned}

So one construction of $H$ is $H=\left(\begin{array}{cccc}{A}_1& A_2& A_3& A_4\\ -A_2& A_1& -A_4& A_3\\ -A_3& A_4& A_1& -A_2\\ -A_4& -A_3& A_2& A_1\end{array}\right)$, where the first row of $A_1,\cdots ,A_4$ are

• $(1,-1,1,-1,1,-1,1)$
• $(1,-1,1,-1,1,-1,1)$
• $(1,-1,1,-1,1,-1,1)$
• $(1,1,1,-1,1,1,1)$.

Now we finish the solution. \end{proof}

2. Suppose that $M$ is an $m\times n$ matrix with 0,1-entries such that the Hamming distance between any two distinct rows is at least $d$, that is, any two rows differ in at least $d$ positions.

• (a) Count triples $(i,j,k)\in [m{]}^2\times [n]$ with $i\ne j$ and $M(i,k)\ne M(j,k)$ in two ways. Conclude that if $2d>n$, then

$$m\le \frac{2d}{2d-n}$$

This is known as Plotkin’s Bound in coding theory.

• (b) Characterize equality in Plotkin’s Bound.
• (c) Suppose that $d=n/2$. Prove that $m\le 2n$ and show that equality holds if and only if there exists a Hadamard matrix of order $n$.

\begin{proof} a) Fix $i$ and $j$, then there are at least $d$ $k$‘s such that $M(i,k)\ne M(j,k)$. Hence $\#(i,j,k)⩾m(m-1)d$. On the other hand, for a fixed $k$, if there are $t$ 0’s and $m-t$ 1’s, then $\#(i,j,k_0)=t(m-t)⩽m^2/2$. Therefore, $m(m-1)d⩽n{m}^2/2$.

b) The number of $0$ and $1$ of each column is same, and Hamming distance is exactly $d$.

c) For a fixed row vector $v$ of $M$, there are $N:=\left(\genfrac{}{}{0ex}{}{n}{0}\right)+\cdots +\left(\genfrac{}{}{0ex}{}{n}{d-1}\right)$ vectors cannot be a row vector of $M$. Hence $mN⩽2^n$. 这个方法走不通

Consider a $1$-$1$ corresponding $f:(x_1,\cdots ,x_n)\to (y_1,\cdots ,y_n)$, where $y_i=x_i$ if $x_i=1$, $y_i=x_i-1$ if $x_i=0$. Then for two row vectors $v_1$ and $v_2$, the Hamming distance between $v_1$ and $v_2$ $⩾d$ iff $⟨f(v_1),f(v_2)⟩⩽0$ when $d=n/2$. The number of $\{v_i:i\in I\}\subseteq {\mathbb{R}}^n$ such that $⟨v_i,v_j⟩⩽0$ is at most $2n$, see ^frvgnt. The equality holds iff $⟨f(v_1),f(v_2)⟩=0$ for all $v_1,v_2$. They form a orthogonal matrix, which deduces a Hadamard matrix. \end{proof}

3. For an Abelian group $G$ of order $v$, we call a $k$-subset $\mathcal{D}\subseteq G$ a $(v,k,\lambda )$-difference set if each nonzero element $g\in G$ occurs exactly $\lambda$ times as a difference $x-y$ for all $x,y\in \mathcal{D}$.

• (a) Let $q=4n-1$ be a prime power. Show that the set of nonzero squares in ${\mathbb{F}}_q$ is a $(4n-1,2n-1,n-1)$-difference set in the additive group ${\mathbb{F}}_q$.
• (b) A difference set with parameters $(4n-1,2n-1,n-1)$ is called Hadamard difference set. Show that any Hadamard difference set gives rise to a Hadamard matrix.

\begin{proof} a) Since ${\mathbb{F}}_q^{\ast }\cong C_{q-1}$ is a cyclic group, the set of nonzero square has cardinality $2n-1$. It suffices to show for any $g$, the number of $(x,y)\in {\mathcal{D}}^2$ such that $x-y=g$ is same. If it holds, then $\lambda =(2n-1)(2n-2)/(4n-2)=n-1$. Define $N(g)=\#\{(x,y)\in {\mathcal{D}}^2:x-y=g\}$. For any square element $s$, we have $N(g)=N(sg)$. Hence $N(g)$ is constant for all $g\in \mathcal{D}$, and $N(h)$ is constant for all $h\notin \mathcal{D}$. Since $-1$ is not a square, we have $N(g)=N(-g)$ and so $N(g)$ is a constant for all $g\in {\mathbb{F}}_q^{\ast }$.

b) Define $M\in {\mathbb{R}}_{(4n-1)\times (4n-1)}$, where $m_{ij}=1$ if $j-i\in \mathcal{D}$; $m_{ij}=0$ if $j-i\notin \mathcal{D}$. Then $M{M}^T=(n-1)J+nI$. Therefore,

$$N=\left(\begin{array}{cc}1& 1\\ 1& J-2M\end{array}\right)$$

satisfying $N{N}^T=4nI$, as $(J-2M)(J-2M{)}^T=-J+4nI$. Now we finish the solution. \end{proof}

4. An affine plane is a rank 2 incidence geometry $\mathcal{A}=(\mathcal{P},\mathcal{L},I)$ that satisfies the following axioms:

• (AP1) Through any two distinct points there is exactly on line.
• (AP2) If $L$ is a line and $P$ is a point outside of $G$, then there is precisely one line through $P$ that has no point common with $L$. (Playfair’s parallel axiom.)
• (AP3) There exist three noncollinear points.
• (a) Let $L_{\infty }$ be a line of a projective plane $\mathcal{G}=(\mathcal{P},\mathcal{L},I)$. Denote the set of points incident with by $L_{\infty }$ by ${\mathcal{P}}_{\infty }$. Show that $\mathcal{A}=\left(\mathcal{P}\backslash {\mathcal{P}}_{\infty },\mathcal{L}\backslash \left\{L_{\infty }\right\},I^{\ast }\right)$ is an affine plane. Here $I^{\ast }$ denotes the natural restriction of $I$ to $\mathcal{A}$.
• (b) In an affine plane, we call two lines $K,L$ parallel they do not intersect. ${}^1$ Show that “being parallel” is an equivalence relation. We call each equivalence class parallel class.
• (c) Given an affine plane $\mathcal{A}=\left({\mathcal{P}}^{\ast },{\mathcal{L}}^{\ast },I^{\ast }\right)$, let $\mathcal{P}$ be ${\mathcal{P}}^{\ast }$ and the parallel classes, and let $\mathcal{L}$ be ${\mathcal{L}}^{\ast }$ and one further line $L_{\infty }$. Furthermore, define $I$ as follows:
  • i. $PIL$ if and only if $P{I}^{\ast }L$ for $P\in {\mathcal{P}}^{\ast },L\in {\mathcal{L}}^{\ast }$,
  • ii. $PI{L}_{\infty }$ for no point $P\in {\mathcal{P}}^{\ast }$,
  • iii. $\Pi IL$ if and only if $L\in \Pi$ for any parallel class $\Pi$ and all $L\in {\mathcal{L}}^{\ast }$,
  • iv. $\Pi I{L}_{\infty }$ for any parallel class $\Pi$.
  • Show that $\mathcal{G}=(\mathcal{P},\mathcal{L},I)$ is a projective plane.

\begin{proof} a) (AP1) is easy, as $p_1,p_2\in \mathcal{P}\setminus {\mathcal{P}}_{\infty }$ is exactly on a line, which is not $L_{\infty }$. (AP2) is easy. If any three points are collinear, then $\mathcal{L}\setminus \{L_{\infty }\}$ contain only one line $L$. Take $v\in L$ and $w\in L_{\infty }$, then there does not exists one line incident with $v$ and $w$, contradiction.

b) $K\sim L$ yields $L\sim K$. If $K\sim L$ and $L\sim M$ and $K\nsim M$, then there exists $v\in K$ and $v\in M$. Then $v\notin L$ and there are two lines has no point common with $L$ and through $P$, contradiction.

c) ${\mathcal{P}}^{\ast }=\mathcal{P}\cup \text{parallel classes}$, ${\mathcal{L}}^{\ast }=\mathcal{L}\cup L_{\infty }$

Every two point incident with a unique line: easy

Every two lines are incident with a unique common point: easy

There are four points, no three collinear: $A,B,{\Pi }_{BC},{\Pi }_{AC}$. \end{proof}

5. Let $\mathcal{A}=(\mathcal{P},\mathcal{L},I)$ be a rank 2 incidence geometry with $\mathcal{P}={\mathbb{R}}^2,\mathcal{L}=(\mathbb{R}\cup \{\infty \})\times \mathbb{R}$, and $P=(x,y)$ incident with $L=(m,b)$ for

• (a) $x=b$ if $m=\infty$,
• (b) $y=\frac{1}{2}mx+b$ if $m\le 0,x\le 0$,
• (c) $y=mx+b$ if $m\ge 0$ or $x\ge 0$.

Show that $\mathcal{A}$ is an affine plane. The plane $\mathcal{A}$ is called the Moulton plane.

\begin{proof} Easy. \end{proof}

6. Let $\mathcal{O}$ be an oval in the projective plane of order $n,n$ even. Show that every point not in $\mathcal{O}$ is incident with precisely 1 or $n+1$ tangents.

\begin{proof} Let $x_i$ be the number of points not in $\mathcal{O}$ incident with $i$ tangents. Then $\sum x_i=n^2$.

Count $(P,L)$ with $P$ exterior point and $L$ tangent and $PIL$. Then $\sum i{x}_i=(n+1)n$.

Now count $(P,L,M)$, where $P$ exterior point, $L,M$ tangent and $PIL,M$. Then $\sum i(i-1)x_i=(n+1)n$.

Thus $\sum i(i-2)x_i=0$. Since $n$ is even, $x_{2k}=0$ and so $-x_1+3x_3+\cdots +(n+1)(n-1)x_{n+1}=0$. Hence $x_1=3x_3+15x_5+\cdots +(n+1)(n-1)x_{n+1}$. If $x_{n+1}\ne 0$, then $x_{n+1}=1$ and $x_1=n^2-1$.

Note that $\sum i(n+2-i)x_i=n^2(n+1)$, where $f(i)=i(n+2-i)$ satisfies $f(1)=f(n+1)=n+1$ and $f(i)>n+1$. Since $\sum (n+1)x_i=n^2(n+1)=\sum i(n+2-i)x_i$, we know $x_3=\cdots =x_{n-1}=0$. Now we finish the proof. \end{proof}