Partial matrices

[math] \newcommand{\mathds}{\mathbb}[/math]

This article was automatically generated from a tex file and may contain conversion errors. If permitted, you may login and edit this article to improve the conversion.

4a. Partial matrices

In this chapter we discuss a number of more specialized questions in the real case, regarding the square or rectangular submatrices of the Hadamard matrices [math]H\in M_N(\pm1)[/math], and some related classes of square or rectangular real matrices. There are many things to be done here, going in various directions, and our plan will be as follows:

(1) We will first review the material from chapter 1 regarding the partial Hadamard matrices, with some further algebraic results, and with a few analytic things added too, inspired from the theory developed in the square matrix case in chapters 2-3.

(2) Then, we will get into the question of counting the partial Hadamard matrices [math]H\in M_{M\times N}(\pm1)[/math], at small values of [math]M[/math], and with [math]N\to\infty[/math]. This is a question having no square counterpart, and following de Launey-Levin , interesting things can be said.

(3) Finally, we will go back to the square matrix case, and present some results from regarding the square submatrices of the usual Hadamard matrices [math]H\in M_N(\pm1)[/math], making the connection with the almost Hadamard matrices from chapter 3.

All in all, many things to be done. Let us mention right away that the most important thing in all this is (2), with the counting result of de Launey and Levin in being something truly remarkable, and providing a viable alternative to the whole HC problematics, developed by countless people since the papers of Sylvester and Hadamard .

Getting started now, let us begin by reviewing what we know about the partial Hadamard matrices, from chapter 1. The definition of these matrices is as follows:

Definition

A partial Hadamard matrix (PHM) is a rectangular matrix

[[math]] H\in M_{M\times N}(\pm1) [[/math]]

whose rows are pairwise orthogonal, with respect to the scalar product of [math]\mathbb R^N[/math].

The motivating examples are the usual Hadamard matrices [math]H\in M_N(\pm1)[/math], and their various [math]M\times N[/math] submatrices, with [math]M\leq N[/math]. However, there are as well examples which are not of this form, and the PHM are interesting combinatorial objects, on their own.

Following the study from the square matrix case, we first have:

Proposition

The set [math]Y_{M,N}[/math] of the [math]M\times N[/math] partial Hadamard matrices is

[[math]] Y_{M,N}=M_{M\times N}(\pm1)\cap\sqrt{N}O_{M,N} [[/math]]

where [math]O_{M,N}[/math] is the following space of rectangular matrices:

[[math]] O_{M,N}=\left\{U\in M_{M\times N}(\mathbb R)\Big|UU^t=1_M\right\} [[/math]]

At [math]M=N[/math], we recover in this way the previous formula [math]Y_N=M_N(\pm1)\cap\sqrt{N}O_N[/math].

Show Proof

This follows exactly as in the square matrix case. Indeed, given a rectangular matrix [math]U\in M_{M\times N}(\mathbb R)[/math] having rows [math]R_1,\ldots,R_M\in\mathbb R^N[/math], we have:

[[math]] (UU^t)_{ij}=\sum_kU_{ik}U_{jk}= \lt R_i,R_j \gt [[/math]]

Thus, the condition [math]UU^t=1_M[/math] expresses the fact that the vectors [math]R_1,\ldots,R_M[/math] are pairwise orthogonal, and of norm 1, and this gives the formula in the statement.

■

As a remark here, at [math]M=1[/math] we have of course [math]Y_{1,N}=M_{1\times N}(\pm1)[/math], and this because of an automatic inclusion [math]M_{1\times N}(\pm1)\subset\sqrt{N}O_{1,N}[/math]. Indeed, given [math]H\in M_{1\times N}(\pm1)[/math], the matrix [math]U=H/\sqrt{N}[/math] satisfies [math]UU^t=\frac{1}{N}\cdot N=1[/math], and so we have, as claimed:

[[math]] U\in\sqrt{N}O_{1,N} [[/math]]

In general, the space [math]O_{M,N}[/math] appearing above can be thought of as being a joint generalization of the unit sphere [math]S^{N-1}[/math], which appears at [math]M=1[/math], and of the orthogonal group [math]O_N[/math], which appears in the square case, [math]M=N[/math]. Based on this analogy, the space [math]O_{M,N}[/math] has several useful interpretations, which can be summarized as follows:

Proposition

The space [math]O_{M,N}[/math] has the following properties:

• Its elements are the transposes of the isometries [math]g:\mathbb R^M\to\mathbb R^N[/math].
• It is the space of vectors [math]R_1,\ldots,R_M\in S^{N-1}[/math] which are pairwise orthogonal.
• It is also an homogeneous space, given by [math]O_{M,N}\simeq O_N/O_{N-M}[/math].
• It is also the space determined by the first [math]M[/math] rows of coordinates on [math]O_N[/math].

Show Proof

All this is standard algebra and geometry, the idea being as follows:

(1) Each matrix [math]U\in M_{M\times N}(\mathbb R)[/math] determines a linear map [math]f:\mathbb R^N\to\mathbb R^M[/math], given by [math]f(x)=Ux[/math], whose transpose is the linear map [math]g:\mathbb R^M\to\mathbb R^N[/math] given by [math]g(x)=U^tx[/math]. Now observe that for any two vectors [math]x,y\in\mathbb R^M[/math] we have:

[[math]] \lt g(x),g(y) \gt = \lt U^tx,U^ty \gt = \lt x,UU^ty \gt [[/math]]

Thus the condition [math]UU^t=1[/math] is equivalent to the following condition:

[[math]] \lt g(x),g(y) \gt = \lt x,y \gt [[/math]]

But this latter condition tells us that [math]g[/math] must be an isometry, as desired.

(2) This follows from the fact, that we know from the proof of Proposition 4.2, that the condition [math]UU^t=1_M[/math] tells us that the row vectors [math]R_1,\ldots,R_M\in\mathbb R^N[/math] of our matrix [math]U\in M_{M\times N}(\mathbb R)[/math] must be pairwise orthogonal, and of norm 1.

(3) Since the condition [math]UU^t=1[/math] defining [math]O_{M,N}[/math] implies [math](UA^t)(UA^t)^t=1[/math], for any orthogonal matrix [math]A\in O_N[/math], we have an action, as follows:

[[math]] O_N\curvearrowright O_{M,N}\quad,\quad A\to[U\to UA^t] [[/math]]

Let us compute now the stabilizer of the following particular element:

[[math]] U=\begin{pmatrix} 1&&0&0&\ldots&0\\ &\ddots\\ 0&&1&0&\ldots&0 \end{pmatrix} [[/math]]

Given an orthogonal matrix [math]A\in O_N[/math], we have the following formula:

[[math]] UA^t=\begin{pmatrix} A_{11}&\ldots&A_{N1}\\ \vdots&&\vdots\\ A_{1M}&\ldots&A_{NM} \end{pmatrix} [[/math]]

Thus [math]U=UA^t[/math] means that the matrix [math]A^t\in O_N[/math] must be of the following form:

[[math]] A^t=\begin{pmatrix} 1_M&0\\ *&* \end{pmatrix} [[/math]]

Now since [math]A^t[/math] is orthogonal, it must be of the following form, with [math]B\in O_{N-M}[/math]:

[[math]] A^t=\begin{pmatrix} 1_M&0\\ 0&B^t \end{pmatrix} [[/math]]

Thus the stabilizer is [math]O_{N-M}[/math], and we obtain [math]O_{M,N}\simeq O_N/O_{N-M}[/math].

(4) This follows from some basic functional analysis. Consider indeed the algebra [math]C(O_N)[/math] of continuous functions [math]f:O_N\to\mathbb C[/math]. By Stone-Weierstrass, this algebra is generated by the coordinate functions [math]u_{ij}:O_N\to\mathbb C[/math], which are given by:

[[math]] u_{ij}(U)=U_{ij} [[/math]]

Consider now the following closed subalgebra of the algebra [math]C(O_N)[/math]:

[[math]] A=\left \lt u_{ij}\Big|i=1,\ldots,M,j=1,\ldots,N\right \gt [[/math]]

We have then [math]A\simeq C(O_{M,N})[/math], coming from the homogeneous space result in (3).

■

Let us discuss now, as a continuation of the study from the real case, some basic analytic aspects. In what regards the 1-norm bound, we have the following result:

Theorem

Given a matrix [math]U\in O_{M,N}[/math] we have

[[math]] ||U||_1\leq M\sqrt{N} [[/math]]

with equality precisely when [math]H=\sqrt{N}U[/math] is partial Hadamard.

Show Proof

We have indeed the following estimate, valid for any [math]U\in O_{M,N}[/math]:

[[math]] \begin{eqnarray*} ||U||_1 &=&\sum_{ij}|U_{ij}|\\ &\leq&\sqrt{MN}\left(\sum_{ij}|U_{ij}|^2\right)^{1/2}\\ &=&M\sqrt{N} \end{eqnarray*} [[/math]]

In this estimate the equality case holds when [math]|U_{ij}|=1/\sqrt{N}[/math] for any [math]i,j[/math]. But this amounts in saying that the rescaled matrix [math]H=\sqrt{N}U[/math] must satisfy [math]H\in M_{M\times N}(\pm1)[/math], and so that this rescaled matrix must be partial Hadamard, as claimed.

■

Observe that in terms of the rescaled matrix [math]H\in\sqrt{N}O_{M,N}[/math], the inequality found above reformulates as [math]||H||_1\leq MN[/math], with equality precisely when [math]H[/math] is partial Hadamard. Thus, in analogy with the square matrix case, we can formulate:

Definition

A matrix [math]H\in\sqrt{N}O_{M,N}[/math] is called:

• Almost PHM, when it locally maximizes the [math]1[/math]-norm on [math]\sqrt{N}O_{M,N}[/math].
• Optimal almost PHM, when it maximizes the [math]1[/math]-norm on [math]\sqrt{N}O_{M,N}[/math].

Some similar estimates hold for the [math]p[/math]-norms, with [math]p\neq2[/math]. The whole subject, while being potentially quite interesting, is for the moment largely unexplored. So, let us turn instead to algebra. Still following the study from the square case, let us formulate:

Definition

Two PHM are called equivalent when we can pass from one to the other by permuting the rows or columns, or multiplying rows or columns by [math]-1[/math]. Also:

• We say that a PHM is in dephased form when its first row and its first column consist of [math]1[/math] entries.
• We say that a PHM is in standard form when it is dephased, with the [math]1[/math] entries moved to the left as much as possible, by proceeding from top to bottom.

Unlike in the square case, where the standard form is generally not used, putting a rectangular matrix in standard form is something quite useful, in practice. As an illustration here, here is a result that we already know, from chapter 1, regarding the partial Hadamard matrices in standard form, at small values of [math]M[/math]:

Proposition

The standard form of dephased PHM at [math]M=2,3,4[/math] is

[[math]] H=\begin{pmatrix}+&+\\\underbrace{+}_{N/2}&\underbrace{-}_{N/2}\end{pmatrix} [[/math]]

[[math]] H=\begin{pmatrix}+&+&+&+\\+&+&-&-\\\underbrace{+}_{N/4}&\underbrace{-}_{N/4}&\underbrace{+}_{N/4}&\underbrace{-}_{N/4}\end{pmatrix} [[/math]]

[[math]] H=\begin{pmatrix} +&+&+&+&+&+&+&+\\ +&+&+&+&-&-&-&-\\ +&+&-&-&+&+&-&-\\ \underbrace{+}_a&\underbrace{-}_b&\underbrace{+}_b&\underbrace{-}_a&\underbrace{+}_b&\underbrace{-}_a&\underbrace{+}_a&\underbrace{-}_b \end{pmatrix} [[/math]]

where the numbers [math]a,b\in\mathbb N[/math] satisfy [math]a+b=N/4[/math].

Show Proof

This is something that we know from chapter 1, the idea being that the [math]M=2[/math] result is obvious, that the [math]M=3[/math] result follows from the orthogonality conditions between the rows, and that the [math]M=4[/math] result follows from the [math]M=3[/math] result.

■

At [math]M=5[/math] and higher the situation is more complicated, and we will be back to this. For the moment, let us stay with [math]M=4[/math]. We can fine-tune our result, as follows:

Theorem

The [math]4\times N[/math] partial Hadamard matrices are of the form

[[math]] H=(\underbrace{W_4\ \ldots\ W_4}_a\ \underbrace{K_4\ \ldots\ K_4}_b) [[/math]]

with [math]a+b=N/4[/math]. Moreover, we can assume [math]a\geq b[/math].

Show Proof

Let [math]H\in M_{4\times N}(\pm1)[/math] be as in Proposition 4.7. The matrix formed by the [math]a[/math] type columns, one from each block, is equivalent to [math]W_4[/math], via a permutation of columns:

[[math]] \begin{pmatrix} +&+&+&+\\ +&+&-&-\\ +&-&+&-\\ +&-&-&+ \end{pmatrix}\sim W_4 [[/math]]

Also, the matrix formed by the [math]b[/math] type columns, one from each block, is equivalent to [math]K_4[/math], via a first column sign switch, plus a certain permutation of the columns:

[[math]] \begin{pmatrix} +&+&+&+\\ +&+&-&-\\ +&-&+&-\\ -&+&+&- \end{pmatrix}\sim K_4 [[/math]]

Thus, just by performing operations on the columns, we obtain, as desired:

[[math]] H\sim(\underbrace{W_4\ \ldots\ W_4}_a\ \underbrace{K_4\ \ldots\ K_4}_b) [[/math]]

In order to prove now the last assertion, we must prove that we have:

[[math]] (\underbrace{W_4\ \ldots\ W_4}_a\ \underbrace{K_4\ \ldots\ K_4}_b)\sim(\underbrace{K_4\ \ldots\ K_4}_a\ \underbrace{W_4\ \ldots\ W_4}_b) [[/math]]

But this can be seen by performing a sign switch on the last row, and then permuting the columns. Equivalently, we can start with the original matrix, in standard form, and perform a sign switch on the last row. The matrix becomes:

[[math]] H\sim\begin{pmatrix} +&+&+&+&+&+&+&+\\ +&+&+&+&-&-&-&-\\ +&+&-&-&+&+&-&-\\ \underbrace{-}_a&\underbrace{+}_b&\underbrace{-}_b&\underbrace{+}_a&\underbrace{-}_b&\underbrace{+}_a&\underbrace{-}_a&\underbrace{+}_b \end{pmatrix} [[/math]]

Now by putting this matrix in standard form, we obtain:

[[math]] H=\begin{pmatrix} +&+&+&+&+&+&+&+\\ +&+&+&+&-&-&-&-\\ +&+&-&-&+&+&-&-\\ \underbrace{+}_b&\underbrace{-}_a&\underbrace{+}_a&\underbrace{-}_b&\underbrace{+}_a&\underbrace{-}_b&\underbrace{+}_b&\underbrace{-}_a \end{pmatrix} [[/math]]

Thus [math]a,b[/math] got interchanged, and this gives the result.

■

At [math]M=5[/math] now, as already mentioned above, the combinatorics becomes quite complicated, and we will see in a moment that there are [math]5\times N[/math] partial Hadamard matrices which do not complete into Hadamard matrices. We first have the following result:

Proposition

The [math]5\times N[/math] partial Hadamard matrices are of the form

[[math]] H=\begin{pmatrix} W_4&\ldots&W_4&&K_4&\ldots&K_4\\ v_1&\ldots&v_a&&x_1&\ldots&x_b \end{pmatrix} [[/math]]

with [math]a\geq b[/math], [math]a+b=N/4[/math] and with [math]v_i,x_j\in(\pm1)^4[/math] satisfying

[[math]] W_4\begin{pmatrix}r_1\\r_2\\r_3\\r_4\end{pmatrix} =-K_4\begin{pmatrix}s_1\\s_2\\s_3\\s_4\end{pmatrix} [[/math]]

where [math]r_t=\sum_i(v_i)_t[/math] and [math]s_t=\sum_j(v_j)_t[/math].

Show Proof

This is something that we already worked out at [math]N=8[/math], in chapter 1, in both of the cases that can appear, namely [math]a=2,b=0[/math] and [math]a=1,b=1[/math]. The proof in general is similar, via some routine computations, with the equations in the statement coming by processing the orthogonality conditions between the 5th row and the first 4 rows.

■

As a first observation, the equations in the above statement can be written in the following more convenient form:

[[math]] K_4^{-1}W_4\begin{pmatrix}r_1\\r_2\\r_3\\r_4\end{pmatrix}=-\begin{pmatrix}s_1\\s_2\\s_3\\s_4\end{pmatrix} [[/math]]

Now observe that the matrix of this system is as follows:

[[math]] K_4^{-1}W_4 =\frac{1}{2}\begin{pmatrix} -&+&+&+\\ -&-&+&-\\ -&+&-&-\\ -&-&-&+ \end{pmatrix} [[/math]]

Thus, the system can be written as follows:

[[math]] \begin{pmatrix} -&+&+&+\\ -&-&+&-\\ -&+&-&-\\ -&-&-&+ \end{pmatrix} \begin{pmatrix}r_1\\r_2\\r_3\\r_4\end{pmatrix} =-2\begin{pmatrix}s_1\\s_2\\s_3\\s_4\end{pmatrix} [[/math]]

Thus, we are led into parity and positivity questions, regarding the vectors [math]r_t=\sum_i(v_i)_t[/math] and [math]s_t=\sum_j(v_j)_t[/math]. It is possible to further go along these lines, but the structure of the [math]5\times N[/math] partial Hadamard matrices remains something quite complicated. As an explicit consequence of our study, however, we have the following result:

Theorem

Consider an arbitrary [math]4\times N[/math] partial Hadamard matrix, written as

[[math]] H=(\underbrace{W_4\ \ldots\ W_4}_a\ \underbrace{K_4\ \ldots\ K_4}_b) [[/math]]

with [math]a\geq b[/math], [math]a+b=N/4[/math], up to equivalence. In order for this matrix to complete into a [math]5\times N[/math] partial Hadamard matrix, the following condition must be satisfied:

[[math]] ab=0\implies N=0(8) [[/math]]

In particular, the following [math]4\times N[/math] partial Hadamard matrix,

[[math]] Z=(W_4\ W_4\ W_4) [[/math]]

does not complete into a [math]5\times N[/math] partial Hadamard matrix.

Show Proof

This follows from Proposition 4.9, because with the notations there, the condition [math]b=0[/math] implies that the system there is simply:

[[math]] W_4\begin{pmatrix}r_1\\r_2\\r_3\\r_4\end{pmatrix}=0 [[/math]]

Since [math]W_4[/math] is invertible, the solution is [math]r=0[/math]. Now observe that, by definition of the numbers [math]r_i[/math], we have [math]r_i=a(2)[/math] for any [math]i[/math]. Thus, we must have [math]a=0(2)[/math], and since we have [math]a=N/4[/math], this gives [math]N=0(8)[/math], as desired. The proof in the case [math]a=0[/math] is similar.

■

In general, the full classification of all the possible [math]5\times 8[/math] completions of a given [math]4\times N[/math] partial Hadamard matrix is something quite difficult, and we have already seen this at [math]N=8[/math], where a careful study is needed, the result being as follows:

Theorem

The two [math]4\times 8[/math] partial Hadamard matrices, namely

[[math]] A=(W_4\ W_4)\quad,\quad B=(W_4\ K_4) [[/math]]

both complete into [math]5\times 8[/math] partial Hadamard matrices, with the solutions being those coming from the lower rows of the following matrices, which are Hadamard:

[[math]] \begin{pmatrix}W_4&W_4\\ W_4&-W_4\end{pmatrix} \quad,\quad \begin{pmatrix}W_4&W_4\\ K_4&-K_4\end{pmatrix}\quad,\quad \begin{pmatrix}W_4&K_4\\ W_4&-K_4\end{pmatrix} \quad,\quad \begin{pmatrix}W_4&K_4\\ K_4&-W_4\end{pmatrix} [[/math]]

This gives as well the higher completions, [math]M\times 8[/math] with [math]M=6,7,8[/math].

Show Proof

This is something that we already know, from chapter 1.

■

At [math]N=12[/math] now, we have only one matrix to be studied, which is as follows, and with at least 8 solutions to the completion problem, coming from the Paley matrix [math]P_{12}[/math]:

[[math]] P=(W_4\ W_4\ K_4) [[/math]]

Generally speaking, all this leads to quite complicated algebra and combinatorics. We refer to Hall , Ito and Verheiden for more on the combinatorics of the PHM. Finally, let us end this discussion with an elementary result, from :

Theorem

For a partial Hadamard matrix [math]H\in M_{(N-1)\times N}(\pm1)[/math], with rows [math]R_1,\ldots,R_{N-1}[/math] and columns [math]C_1,\ldots,C_N[/math], the following are equivalent:

• [math]H[/math] is completable into a [math]N\times N[/math] Hadamard matrix.
• [math]|\det H^{(j)}|[/math] is independent from [math]j[/math], where [math]H^{(j)}[/math] is obtained from [math]H[/math] by removing [math]C_j[/math].
• [math]|\det H^{(j)}|=N^{N/2-1}[/math] for any [math]i[/math], where [math]H^{(j)}[/math] is as above.

Moreover, if these conditions hold, the completion is obtained by setting

[[math]] H_{Nj} = (-1)^{j}N^{1-N/2}\,\det H^{(j)} [[/math]]

with [math]H^{(j)}[/math] being as above, obtained from [math]H[/math] by removing the column [math]C_j[/math].

Show Proof

This follows from some basic linear algebra, the idea being as follows:

[math](1)\iff(2)[/math]. Consider the following vector, having integer entries:

[[math]] Z_j=(-1)^j\,\det H^{(j)} [[/math]]

Our claim is that we have the following equality of vector spaces:

[[math]] span(R_1,\ldots,R_{N-1})^\perp=\{\lambda Z|\lambda \in \mathbb R\} [[/math]]

Indeed, if we denote by [math]H_i[/math] the square matrix obtained from [math]H[/math] by adding a first row equal to [math]R_i[/math], then we have the following computation, which proves our claim:

[[math]] \begin{eqnarray*} \lt R_i,Z \gt &=&\sum_jH_{ij}Z_j\\ &=&\sum_j(-1)^jH_{ij}\det H^{(j)}\\ &=&\det H_i\\ &=&0 \end{eqnarray*} [[/math]]

But this gives [math](1)\iff(2)[/math], since the existence of a completion is equivalent to the fact that [math]span(R_1,\ldots,R_{N-1})^\perp[/math] contains a vector with all entries having absolute value [math]1[/math].

[math](1)\implies(3)[/math]. Write [math]c=|\det H^{(j)}|[/math] and let [math]M\in M_N(\pm1)[/math] be the Hadamard matrix completing [math]H[/math]. The proof of [math](1)\iff(2)[/math] above shows that the last row of [math]M[/math] must be the vector [math]c^{-1} Z[/math]. Also, since the matrix [math]M\in M_N(\pm1)[/math] is Hadamard, we have:

[[math]] |\det M|=N^{N/2} [[/math]]

Thus, it remains to compute this determinant by expansion with respect to the last row, and the computation here gives:

[[math]] \begin{eqnarray*} \det M &=&\sum_{j=1}^N c^{-1} (-1)^{N+j} (-1)^j\det H^{(j)}\cdot\det H^{(j)}\\ &=&(-1)^N c N \end{eqnarray*} [[/math]]

But this means that we have [math]c= N^{N/2-1}[/math], which proves the implication [math](1)\implies(3)[/math], and also proves the last assertion of our theorem.

[math](3)\implies(2)[/math]. This is something obvious, and so we are done.

■

We will be back to the algebraic properties of the PHM on several occasions in this book, but directly in the complex matrix case, or sometimes in the general root of unity case, where more things can be said. In relation with the real case, of particular interest will be the material in chapter 15 below, where, following , we will associate a quantum semigroup of partial permutations of [math]\{1,\ldots,N\}[/math] to each such matrix, real or complex.

4b. Counting results

Let us try now to count the partial Hadamard matrices [math]H\in M_{M\times N}(\pm1)[/math]. This is an easy task at [math]M=2,3,4[/math], where the answer is as follows:

Proposition

The number of PHM at [math]M=2,3,4[/math] is

[[math]] \begin{eqnarray*} \#PHM_{2\times N}&=&2^N\binom{N}{N/2}\\ \#PHM_{3\times N}&=&2^N\binom{N}{N/4,N/4,N/4,N/4}\\ \#PHM_{4\times N}&=&2^N\sum_{a+b=N/4}\binom{N}{a,b,b,a,b,a,a,b} \end{eqnarray*} [[/math]]

with the quantities on the right being multinomial coefficients.

Show Proof

We use the structure results for the PHM in standard form at [math]M\leq4[/math] found above, which are as follows, with the numbers [math]a,b\in\mathbb N[/math] satisfing [math]a+b=N/4[/math]:

[[math]] H=\begin{pmatrix}+&+\\\underbrace{+}_{N/2}&\underbrace{-}_{N/2}\end{pmatrix} [[/math]]

[[math]] H=\begin{pmatrix}+&+&+&+\\+&+&-&-\\\underbrace{+}_{N/4}&\underbrace{-}_{N/4}&\underbrace{+}_{N/4}&\underbrace{-}_{N/4}\end{pmatrix} [[/math]]

[[math]] H=\begin{pmatrix} +&+&+&+&+&+&+&+\\ +&+&+&+&-&-&-&-\\ +&+&-&-&+&+&-&-\\ \underbrace{+}_a&\underbrace{-}_b&\underbrace{+}_b&\underbrace{-}_a&\underbrace{+}_b&\underbrace{-}_a&\underbrace{+}_a&\underbrace{-}_b \end{pmatrix} [[/math]]

But this gives the formulae in the statement, with the multinomial coefficients counting the matrices having the first row consisting of 1 entries only, obtained by permuting the columns of the above solutions, and with the [math]2^N[/math] factors coming from this.

■

In order to convert the above result into [math]N\to\infty[/math] estimates, we will need the following technical result regarding the multinomial coefficients, from Richmond-Shallit :

Theorem

We have the estimate

[[math]] \sum_{n_1+\ldots+n_k=N}\binom{N}{n_1,\ldots,n_k}^p \simeq k^{pN}\sqrt{\frac{k^{k(p-1)}}{p^{k-1}(2\pi N)^{(k-1)(p-1)}}} [[/math]]

in the [math]N\to\infty[/math] limit.

Show Proof

This is proved by Richmond and Shallit in at [math]p=2[/math], and the proof in the general case, [math]p\in\mathbb N[/math], is similar, the idea being as follows:

(1) In order to do some analysis, we agree to use the convention [math]x!=\Gamma(x+1)[/math] for [math]x \gt 0[/math] real. Since the multinomial coefficient in the statement attains its maximum when the numbers [math]n_i[/math] are all equal, it is natural to make a change of variables, as follows:

[[math]] n_i=\frac{N}{k}+\sqrt{N}x_i [[/math]]

Observe that, since we have [math]n_1+\ldots+n_k=N[/math], the numbers [math]x_1,\ldots,x_k[/math] satisfy:

[[math]] x_1+\ldots+x_k=0 [[/math]]

(2) Let us first estimate, in terms of the numbers [math]x_1,\ldots,x_k[/math], the multinomial coefficient in the statement. By using the Taylor formula [math]\log(1+y)\simeq y-y^2/2[/math], we obtain:

[[math]] \begin{eqnarray*} \log n_i &=&\log\left(\frac{N}{k}\left(1+\frac{kx_i}{\sqrt{N}}\right)\right)\\ &\simeq&\log\frac{N}{k}+\frac{kx_i}{\sqrt{N}}-\frac{k^2x_i^2}{2N} \end{eqnarray*} [[/math]]

By multiplying by [math]n_i[/math], this gives the following estimate:

[[math]] \begin{eqnarray*} n_i\log n_i &\simeq&\left(\frac{N}{k}+\sqrt{N}x_i\right)\log\frac{N}{k}+\left(\frac{N}{k}+\sqrt{N}x_i\right)\left(\frac{kx_i}{\sqrt{N}}-\frac{k^2x_i^2}{2N}\right)\\ &\simeq&\left(\frac{N}{k}+\sqrt{N}x_i\right)\log\frac{N}{k}+\sqrt{N}x_i+\frac{kx_i^2}{2} \end{eqnarray*} [[/math]]

Now by further substracting [math]n_i[/math], we obtain the following estimate:

[[math]] n_i\log n_i-n_i \simeq\left(\frac{N}{k}+\sqrt{N}x_i\right)\log\frac{N}{k}+\frac{kx_i^2}{2}-\frac{N}{k} [[/math]]

(3) We are now ready to estimate the multinomial coefficient in the statement. By summing over [math]i[/math], and using [math]x_1+\ldots+x_k=0[/math], the formula found above gives:

[[math]] \sum_in_i\log n_i-n_i\simeq N\log\frac{N}{k}-N+\frac{k}{2}\sum_ix_i^2 [[/math]]

By using the Stirling formula [math]n!\simeq e^{n\log n-n}\sqrt{2\pi n}[/math], we obtain from this:

[[math]] \begin{eqnarray*} n_1!\ldots n_k! &\simeq&\exp\left(\sum_in_i\log n_i-n_i\right)\sqrt{2\pi n_1}\ldots\sqrt{2\pi n_k}\\ &\simeq&\exp\left(N\log\frac{N}{k}-N+\frac{k}{2}\sum_ix_i^2\right)\left(\frac{2\pi N}{k}\right)^{k/2}\\ &=&\left(\frac{N}{ke}\right)^N\exp\left(\frac{k}{2}\sum_ix_i^2\right)\left(\frac{2\pi N}{k}\right)^{k/2} \end{eqnarray*} [[/math]]

Thus, the multinomial coefficient in the statement is:

[[math]] \begin{eqnarray*} \binom{N}{n_1,\ldots,n_k} &\simeq&\left(\frac{N}{e}\right)^N\sqrt{2\pi N}\left(\frac{ke}{N}\right)^N\exp\left(-\frac{k}{2}\sum_ix_i^2\right)\left(\frac{2\pi N}{k}\right)^{-k/2}\\ &=&k^N\exp\left(-\frac{k}{2}\sum_ix_i^2\right)(2\pi N)^{(1-k)/2}k^{k/2} \end{eqnarray*} [[/math]]

(4) Raising now to the power [math]p[/math] gives the following formula:

[[math]] \binom{N}{n_1,\ldots,n_k}^p\simeq k^{pN}\exp\left(-\frac{kp}{2}\sum_ix_i^2\right)(2\pi N)^{(1-k)p/2}k^{kp/2} [[/math]]

Getting now to what we want to do, the point is that, by using the above estimate for the summands, we can estimate their sum by a multiple integral, as follows:

[[math]] \begin{eqnarray*} &&\sum_{n_1+\ldots+n_k=N}\binom{N}{n_1,\ldots,n_k}^p\\ &\simeq&k^{pN}(2\pi N)^{\frac{(1-k)p}{2}}k^{\frac{kp}{2}}\int_0^N\ldots\int_0^N\exp\left(-\frac{kp}{2}\sum_{i=1}^kx_i^2\right)dn_1\ldots dn_{k-1}\\ &=&k^{pN}(2\pi N)^{\frac{(1-k)p}{2}}k^{\frac{kp}{2}}N^{\frac{k-1}{2}}\\ &&\times\int_0^N\ldots\int_0^N\exp\left(-\frac{kp}{2}\sum_{i=1}^{k-1}x_i^2-\frac{kp}{2}\left(\sum_{i=1}^{k-1}x_i\right)^2\right)dx_1\ldots dx_{k-1} \end{eqnarray*} [[/math]]

(5) We are almost there. By doing the calculus, as explained in , this gives:

[[math]] \begin{eqnarray*} \sum_{n_1+\ldots+n_k=N}\binom{N}{n_1,\ldots,n_k}^p &\simeq&k^{pN}(2\pi N)^{\frac{(1-k)p}{2}}k^{\frac{kp}{2}}N^{\frac{k-1}{2}}\times\pi^{\frac{k-1}{2}}k^{-\frac{1}{2}}\left(\frac{kp}{2}\right)^{\frac{1-k}{2}}\\ &=&k^{pN}(2\pi N)^{\frac{(1-k)p}{2}}k^{\frac{kp}{2}-\frac{1}{2}+\frac{1-k}{2}}\left(\frac{p}{2\pi N}\right)^{\frac{1-k}{2}}\\ &=&k^{pN}(2\pi N)^{\frac{(1-k)(p-1)}{2}}k^{\frac{kp-k}{2}}p^{\frac{1-k}{2}}\\ &=&k^{pN}\sqrt{\frac{k^{k(p-1)}}{p^{k-1}(2\pi N)^{(k-1)(p-1)}}} \end{eqnarray*} [[/math]]

Thus we have obtained the formula in the statement, and we are done.

■

The above formula is something very useful, that we will heavily use in what follows. Getting back now to the PHM, we have the following result:

Theorem

The probability for a random [math]H\in M_{M\times N}(\pm1)[/math] to be a PHM is

[[math]] P_2\simeq\frac{2}{\sqrt{2\pi N}}\quad,\quad P_3\simeq\frac{16}{\sqrt{(2\pi N)^3}}\quad,\quad P_4\simeq\frac{512}{(2\pi N)^3} [[/math]]

in the [math]N\in4\mathbb N[/math], [math]N\to\infty[/math] limit.

Show Proof

Since there are exactly [math]2^{MN}[/math] sign matrices of size [math]N\times M[/math], the probability [math]P_M[/math] for a random [math]H\in M_{M\times N}(\pm1)[/math] to be a PHM is given by:

[[math]] P_M=\frac{1}{2^{MN}}\#PHM_{M\times N} [[/math]]

With this formula in hand, the result follows from Proposition 4.13, by using the estimates for sums of multinomial coefficients from Theorem 4.14.

■

4c. Asymptotic count

In their remarkable paper , de Launey and Levin were able to count the PHM, in the asymptotic limit [math]N\in 4\mathbb N[/math], [math]N\to\infty[/math]. Their method is based on:

Proposition

The probability for a random [math]H\in M_{M\times N}(\pm1)[/math] to be partial Hadamard equals the probability for a length [math]N[/math] random walk with increments drawn from

[[math]] E=\left\{(e_i\bar{e}_j)_{i \lt j}\Big|e\in\mathbb Z_2^M\right\} [[/math]]

regarded as a subset of [math]\mathbb Z_2^{\binom{M}{2}}[/math] to return at the origin.

Show Proof

Indeed, with [math]T(e)=(e_i\bar{e}_j)_{i \lt j}[/math], a matrix [math]X=[e_1,\ldots,e_N]\in M_{M\times N}(\mathbb Z_2)[/math] is partial Hadamard precisely when [math]T(e_1)+\ldots+T(e_N)=0[/math]. But this gives the result.

■

As explained in , the above probability can be indeed computed, and we have:

Theorem

The probability for a random [math]H\in M_{M\times N}(\pm1)[/math] to be PHM is

[[math]] P_M\simeq\frac{2^{(M-1)^2}}{\sqrt{(2\pi N)^{\binom{M}{2}}}} [[/math]]

in the [math]N\in 4\mathbb N[/math], [math]N\to\infty[/math] limit.

Show Proof

According to Proposition 4.16, we have:

[[math]] \begin{eqnarray*} P_M &=&\frac{1}{q^{(M-1)N}}\#\left\{\xi_1,\ldots,\xi_N\in E\Big|\sum_i\xi_i=0\right\}\\ &=&\frac{1}{q^{(M-1)N}}\sum_{\xi_1,\ldots,\xi_N\in E}\delta_{\Sigma\xi_i,0} \end{eqnarray*} [[/math]]

By using the Fourier inversion formula we have, with [math]D=\binom{M}{2}[/math]:

[[math]] \delta_{\Sigma\xi_i,0}=\frac{1}{(2\pi)^D}\int_{[-\pi,\pi]^D}e^{i \lt \lambda,\Sigma\xi_i \gt }d\lambda [[/math]]

After many non-trivial computations, this leads to the result. See .

■

All this is quite interesting, because it provides a viable alternative to the HC problematics. To be more precise, after long decades of work on the HC, the conclusion that emerges is that this is probably an analytic question, at least in the [math]N \gt \gt 0[/math] regime, with the thing to be done being that of conjecturing something of type [math]C_N\simeq f(N)[/math] about the asymptotics of the number [math]C_N[/math] of the [math]N\times N[/math] Hadamard matrices, with [math]f(N)[/math] being some kind of known function, and then proving this conjecture, with [math]C_N \gt 0[/math] coming as consequence. But, no one knows what the conjecture of type [math]C_N\simeq f(N)[/math] should be.

In contrast to this, the work of de Launey and Levin explained above puts us on a clear track, in order to deal with such questions. Indeed, when enlarging the attention to the partial Hadamard matrices [math]H\in M_{M\times N}(\pm1)[/math], we do have their counting result, at any [math]M\in\mathbb N[/math], and in the [math]N\to\infty[/math] limit, as a non-trivial and rock-solid starting point, and the problem is that of slowly fine-tuning their methods, as to get towards asymptotic counting results in the square matrix case, [math]M=N[/math]. But this is a quite tough mix of probability and combinatorics, and no one managed so far to go beyond .

4d. Square submatrices

Following now , and some previous work of Koukouvinos, Mitrouli, Seberry and Szöllősi , let us discuss now another topic, namely the square submatrices of the usual, square Hadamard matrices. We will see that all this is related, in a quite subtle way, to the notion of almost Hadamard matrix (AHM), discussed in chapter 3. Let us start with some basic linear algebra. We will need the following standard result:

Theorem

Any matrix [math]D\in M_N(\mathbb R)[/math] can be written as

[[math]] D=UT [[/math]]

with positive semidefinite [math]T=\sqrt{D^tD}[/math], and with orthogonal [math]U\in O_N[/math]. Moreover:

• If [math]D[/math] is invertible, then [math]U[/math] is uniquely determined, and we write:
  [[math]] U=Pol(D) [[/math]]
• If [math]D=V\Delta W^t[/math] with [math]V,W[/math] being orthogonal and [math]\Delta[/math] being diagonal is the singular value decomposition of [math]D[/math], then [math]Pol(D)=VW^t[/math].

Show Proof

All this is very standard, and can be found in any linear algebra book, one method for instance being that of deducing (2), and then the whole result, from the singular value decomposition theorem for the matrices [math]D\in M_N(\mathbb R)[/math].

■

We start analyzing the square submatrices of the Hadamard matrices. By permuting rows and columns, we can always reduce the problem to the following situation:

Definition

[math]D\in M_d(\pm1)[/math] is called a submatrix of [math]H\in M_N(\pm1)[/math] if we have

[[math]] H=\begin{pmatrix}A&B\\C&D\end{pmatrix} [[/math]]

up to a permutation of the rows and columns of [math]H[/math]. In this case we set:

[[math]] r=size(A)=N-d [[/math]]

Observe that any [math]D\in M_2(\pm1)[/math] having distinct columns appears as a submatrix of [math]W_4[/math], and that any [math]D\in M_2(\pm1)[/math] appears as a submatrix of [math]W_8[/math]. In fact, we have:

Proposition

Let [math]D\in M_d(\pm1)[/math] be an arbitrary sign matrix.

• If [math]D[/math] has distinct columns, then [math]D[/math] is as submatrix of [math]W_N[/math], with [math]N=2^d[/math].
• In general, [math]D[/math] appears as submatrix of [math]W_M[/math], with [math]M=2^{d+[\log_2d]}[/math].

Show Proof

This is something elementary, as follows:

(1) Set [math]N=2^d[/math]. If we use length [math]d[/math] bit strings [math]x,y\in\{0,1\}^d[/math] as indices, then:

[[math]] (W_N)_{xy}=(-1)^{\sum x_iy_i} [[/math]]

Let [math]\widetilde{W}_N\in M_{d\times N}(\pm1)[/math] be the submatrix of [math]W_N[/math] having as row indices the strings of the following type:

[[math]] x_i=(\underbrace{0\ldots 0}_i\,1\,\underbrace{0\ldots0}_{N-i-1}) [[/math]]

Then for [math]i\in\{1,\ldots,d\}[/math] and [math]y\in\{0,1\}^d[/math], we have: \vskip-3mm

[[math]] (\widetilde{W}_N)_{iy}=(-1)^{y_i} [[/math]]

Thus the columns of [math]\widetilde{W}_N[/math] are the [math]N[/math] elements of [math]\{\pm 1\}^d[/math], which gives the result.

(2) Set [math]R=2^{[\log_2d]}\geq d[/math]. Since the first row of [math]W_R[/math] contains only ones, [math]W_R\otimes W_N[/math] contains as a submatrix [math]R[/math] copies of [math]\widetilde{W}_N[/math], in which [math]D[/math] can be embedded, as desired.

■

Let us go back now to Definition 4.19, and try to relate the matrices [math]A,D[/math] appearing there. The following result, due to Szòllősi , is a first one in this direction:

Theorem

Assuming that a square matrix

[[math]] U=\begin{pmatrix}A&B\\C&D\end{pmatrix} [[/math]]

is unitary, with [math]A\in M_r(\mathbb C)[/math], [math]D\in M_d(\mathbb C)[/math], then:

• The singular values of [math]A,D[/math] are identical, up to [math]|r-d|[/math] values of [math]1[/math].
• [math]\det A=\det U\cdot\overline{\det D}[/math], so in particular, [math]|\det A|=|\det D|[/math].

Show Proof

Here is a simplified proof. From the unitarity of [math]U[/math] we get:

[[math]] \begin{align*} A^*A+C^*C&=I_r\\ CC^*+DD^*&=I_d\\ AC^*+BD^*&=0_{r\times d} \end{align*} [[/math]]

(1) This follows from the first two equations, and from the well-known fact that the matrices [math]CC^*,C^*C[/math] have the same eigenvalues, up to [math]|r-d|[/math] values of [math]0[/math].

(2) By using the above unitarity equations, we have:

[[math]] \begin{pmatrix}A&0\\C&I\end{pmatrix} =\begin{pmatrix}A&B\\C&D\end{pmatrix} \begin{pmatrix}I&C^*\\0&D^*\end{pmatrix} [[/math]]

The result follows then by taking determinants.

■

We want to find a formula for the polar decomposition of [math]D[/math]. Let us introduce:

Definition

Associated to any [math]A\in M_r(\pm1)[/math] are the matrices

[[math]] \begin{eqnarray*} X_A&=&(\sqrt{N}I_r+\sqrt{A^tA})^{-1}Pol(A)^t\\ Y_A&=&(\sqrt{N}I_r+\sqrt{AA^t})^{-1} \end{eqnarray*} [[/math]]

depending on a parameter [math]N[/math].

Observe that, in terms of the polar decomposition [math]A=VP[/math], we have:

[[math]] \begin{eqnarray*} X_A&=&(\sqrt{N}+P)^{-1}V^t\\ Y_A&=&V(\sqrt{N}+P)^{-1}V^t \end{eqnarray*} [[/math]]

The idea now will be that, under the assumptions of Theorem 4.21, the polar parts of the matrices [math]A,D[/math] appearing there should be related by a simple formula, with the passage [math]Pol(A)\to Pol(D)[/math] involving the above matrices [math]X_A,Y_A[/math].

In what follows we will focus on the case where [math]U\in U_N[/math] is replaced by [math]U=\sqrt{N}H[/math] with [math]H\in M_N(\pm1)[/math] Hadamard. In the non-singular case, following , we have:

Proposition

Assuming that a square matrix

[[math]] H=\begin{pmatrix}A&B\\C & D\end{pmatrix}\in M_N(\pm1) [[/math]]

is Hadamard, with [math]A\in M_r(\pm1)[/math] invertible, [math]D\in M_d(\pm1)[/math], and [math]||A|| \lt \sqrt N[/math], the polar decomposition [math]D=UT[/math] is given by the formulae

[[math]] U=\frac{1}{\sqrt{N}}(D-E)\quad,\quad T=\sqrt{N}I_d-S [[/math]]

where [math]E=CX_AB[/math] and [math]S=B^tY_AB[/math].

Show Proof

Since [math]H[/math] is Hadamard, we can use the formulae coming from:

[[math]] \begin{pmatrix}A&B\\C&D\end{pmatrix} \begin{pmatrix}A^t&C^t\\B^t&D^t\end{pmatrix} =\begin{pmatrix}A^t&C^t\\B^t&D^t\end{pmatrix} \begin{pmatrix}A&B\\C&D\end{pmatrix} =\begin{pmatrix}N&0\\0&N\end{pmatrix} [[/math]]

We start from the singular value decomposition of [math]A[/math]:

[[math]] A=Vdiag(s_i)X^t [[/math]]

Here [math]V,X \in O_r[/math] and [math]s_i\in(0,||A||][/math]. From [math]AA^t+BB^t=NI_r[/math] we get:

[[math]] BB^t=Vdiag(N-s_i^2)V^t [[/math]]

Thus, the singular value decomposition of [math]B[/math] is as follows, with [math]Y\in O_d[/math]:

[[math]] B=V\begin{pmatrix}diag(\sqrt{N-s_i^2})&0_{r\times(d-r)}\end{pmatrix}Y^t [[/math]]

Similarly, from [math]A^tA+C^tC=I_r[/math] we deduce the singular value decomposition for [math]C[/math], the result being that there exists an orthogonal matrix [math]\widetilde{Z}\in O_d[/math] such that:

[[math]] C=-\widetilde Z\begin{pmatrix}diag(\sqrt{N-s_i^2})\\0_{(d-r)\times r}\end{pmatrix}X^t [[/math]]

From [math]B^tB+D^tD=NI_d[/math] we obtain:

[[math]] D^tD = Y (diag(s_i^2)\oplus NI_{(d-r)})Y^t [[/math]]

Thus the polar decomposition of [math]D[/math] reads:

[[math]] D=UY(diag(s_i)\oplus\sqrt NI_{(d-r)})Y^t [[/math]]

Let [math]Z=UY[/math]. By using the orthogonality relation [math]CA^t+DB^t=0_{d \times r}[/math], we obtain:

[[math]] \widetilde Z \begin{pmatrix}diag(s_i\sqrt{N-s_i^2})\\0_{(d-r)\times r}\end{pmatrix} =Z\begin{pmatrix}diag(s_i\sqrt{N-s_i^2})\\0_{(d-r)\times r}\end{pmatrix} [[/math]]

From the assumptions of our theorem, we have the following inequality:

[[math]] s_i\sqrt{N-s_i^2} \gt 0 [[/math]]

Thus [math]Z^t\widetilde Z = I_r \oplus Q[/math], for some orthogonal matrix [math]Q \in O_d[/math]. Plugging [math]\widetilde Z = Z(I_r \oplus Q)[/math] in the singular value decomposition formula for [math]C[/math], we obtain:

[[math]] \begin{eqnarray*} C &=&-Z(I_r \oplus Q)\begin{pmatrix}diag(\sqrt{N-s_i^2})\\0_{(d-r)\times r}\end{pmatrix}X^t\\ &=&-Z\begin{pmatrix}diag(\sqrt{N-s_i^2})\\0_{(d-r)\times r}\end{pmatrix}X^t \end{eqnarray*} [[/math]]

To summarize, we have found [math]V,X \in O_r[/math] and [math]Y,Z \in O_d[/math] such that:

[[math]] \begin{align*} A &=Vdiag(s_i)X^t\\ B &= V\begin{pmatrix}diag(\sqrt{N-s_i^2})&0_{r\times(d-r)} \end{pmatrix}Y^t\\ C &=-Z\begin{pmatrix}diag(\sqrt{N-s_i^2})\\0_{(d-r)\times r}\end{pmatrix}X^t\\ D &= Z (diag(s_i)\oplus \sqrt N I_{(d-r)}) Y^t \end{align*} [[/math]]

Now with [math]U,T,E,S[/math] defined as in the statement, we obtain:

[[math]] \begin{eqnarray*} U&=&ZY^t\\ E&=&Z(diag(\sqrt{N}-s_i)\oplus0_{d-r})Y^t\\ \sqrt{A^tA}&=&Xdiag(s_i)X^t\\ (\sqrt{N}I_r+\sqrt{A^tA})^{-1}&=&Xdiag(1/(\sqrt{N}+s_i))X^t\\ X_A&=&Xdiag(1/(\sqrt{N}+s_i))V^t\\ CX_AB&=&Z(diag(\sqrt{N}-s_i)\oplus0_{d-r})Y^t \end{eqnarray*} [[/math]]

Thus we have [math]E=CX_AB[/math], as claimed. Also, we have:

[[math]] \begin{eqnarray*} T&=&Y(diag(s_i)\oplus\sqrt{N}I_{d-r})Y^t\\ S&=&Y(diag(\sqrt{N}-s_i)\oplus0_{d-r})Y^t\\ \sqrt{AA^t}&=&Vdiag(s_i)V^t\\ Y_A&=&Vdiag(1/(\sqrt{N}+s_i))V^t\\ B^tY_AB&=&Y(diag(\sqrt{N}-s_i)\oplus0_{d-r})Y^t \end{eqnarray*} [[/math]]

Thus, we have as well [math]S=B^tY_AB[/math], as claimed, and we are done.

■

Observe that, in the above statement, in the case where the size of the upper left block satisfies [math]r \lt \sqrt N[/math], the condition [math]||A|| \lt \sqrt N[/math] is automatically satisfied. Our claim now is that all this is related to the notion of almost Hadamard matrix, from chapter 3. To be more precise, still following , let us introduce the following notion:

Definition

A sign matrix [math]S\in M_N(\pm1)[/math] is called an almost Hadamard sign pattern (AHP) if it appears as

[[math]] S_{ij}=sgn(H_{ij}) [[/math]]

for a certain almost Hadamard matrix [math]H\in M_N(\mathbb R)[/math].

Observe that, due to the theory in chapter 3, if a sign matrix [math]S[/math] is an AHP, then there exists a unique almost Hadamard matrix [math]H[/math] such that [math]S_{ij}=sgn(H_{ij})[/math], namely:

[[math]] H =\sqrt{N}Pol(S) [[/math]]

Getting back to Proposition 4.23, let us try to find out when [math]D[/math] is AHP. For this purpose, we must estimate the quantity [math]||E||_\infty=\max_{ij}|E_{ij}|[/math], and we have here:

Proposition

Assuming that a matrix

[[math]] H=\begin{pmatrix}A&B\\C & D\end{pmatrix}\in M_N(\pm1) [[/math]]

is an Hadamard matrix, with [math]A\in M_r(\pm1)[/math], [math]D\in M_d(\pm1)[/math] and [math]r\leq d[/math], then

[[math]] Pol(D)=\frac{1}{\sqrt{N}}(D-E) [[/math]]

with [math]E[/math] satisfying:

• [math]||E||_\infty\leq\frac{r\sqrt{r}}{\sqrt{r}+\sqrt{N}}[/math] when [math]A[/math] is Hadamard.
• [math]||E||_\infty\leq\frac{r^2c\sqrt{N}}{N-r^2}[/math] if [math]r^2 \lt N[/math], with [math]c=||Pol(A)-\frac{A}{\sqrt{N}}||_\infty[/math].
• [math]||E||_\infty\leq\frac{r^2(1+\sqrt{N})}{N-r^2}[/math] if [math]r^2 \lt N[/math].

Show Proof

We use the basic fact that for two rectangular matrices which are multipliable, [math]X\in M_{p\times r}(\mathbb C)[/math] and [math]Y\in M_{r\times q}(\mathbb C)[/math], we have the following estimate:

[[math]] ||XY||_\infty\leq r||X||_\infty||Y||_\infty [[/math]]

Thus, according to Proposition 4.23, we have:

[[math]] \begin{eqnarray*} ||E||_\infty &=&||CX_AB||_\infty\\ &\leq&r^2||C||_\infty||X_A||_\infty||B||_\infty\\ &=&r^2||X_A||_\infty \end{eqnarray*} [[/math]]

(1) If [math]A[/math] is Hadamard, [math]AA^t =rI_r[/math], [math]Pol(A)=A/\sqrt{r}[/math] and thus:

[[math]] \begin{eqnarray*} X_A &=&(\sqrt{N}I_r+\sqrt{r}I_r)^{-1}\frac{A^t}{\sqrt{r}}\\ &=&\frac{A^t}{r+\sqrt{rN}} \end{eqnarray*} [[/math]]

We therefore obtain from this:

[[math]] ||X_A||_\infty=\frac{1}{r+\sqrt{rN}} [[/math]]

But this gives the result.

(2) According to the definition of [math]X_A[/math], we have:

[[math]] \begin{eqnarray*} X_A &=&(\sqrt{N}I_r+\sqrt{A^tA})^{-1}Pol(A)^t\\ &=&(NI_r-A^tA)^{-1}(\sqrt{N}I_r-\sqrt{A^tA})Pol(A)^t\\ &=&(NI_r-A^tA)^{-1}(\sqrt{N}Pol(A)-A)^t \end{eqnarray*} [[/math]]

We therefore obtain the following estimate:

[[math]] \begin{eqnarray*} ||X_A||_\infty &\leq&r||(NI_r-A^tA)^{-1}||_\infty||\sqrt{N}Pol(A)-A||_\infty\\ &=&\frac{rc}{\sqrt{N}}\Big|\Big|\left(I_r-\frac{A^tA}{N}\right)^{-1}\Big|\Big|_\infty \end{eqnarray*} [[/math]]

Now by using [math]||A^tA||_\infty\leq r[/math], we obtain:

[[math]] \begin{eqnarray*} \Big|\Big|\left(I_r-\frac{A^tA}{N}\right)^{-1}\Big|\Big|_\infty &\leq&\sum_{k=0}^\infty\frac{||(A^tA)^k||_\infty}{N^k}\\ &\leq&\sum_{k=0}^\infty\frac{r^{2k-1}}{N^k}\\ &=&\frac{1}{r}\cdot\frac{1}{1-r^2/N}\\ &=&\frac{N}{rN-r^3} \end{eqnarray*} [[/math]]

Thus we have the following estimate:

[[math]] ||X_A||_\infty \leq\frac{rc}{\sqrt{N}}\cdot\frac{N}{rN-r^3} =\frac{c\sqrt{N}}{N-r^2} [[/math]]

But this gives the result.

(3) This follows from (2), because:

[[math]] c \leq||Pol(A)||_\infty+||A/\sqrt{N}||_\infty \leq1+\frac{1}{\sqrt{N}} [[/math]]

The proof is now complete.

■

Following , we can now state and prove a main result, as follows:

Theorem

Assume that a matrix

[[math]] H=\begin{pmatrix}A&B\\C & D\end{pmatrix} [[/math]]

is Hadamard, with [math]A\in M_r(\pm1),H\in M_N(\pm1)[/math].

• If [math]A[/math] is Hadamard, and [math]N \gt r(r-1)^2[/math], then [math]D[/math] is AHP.
• If [math]N \gt \frac{r^2}{4}(x+\sqrt{x^2+4})^2[/math], where [math]x=r||Pol(A)-\frac{A}{\sqrt{N}}||_\infty[/math], then [math]D[/math] is AHP.
• If [math]N \gt \frac{r^2}{4}(r+\sqrt{r^2+8})^2[/math], then [math]D[/math] is AHP.

Show Proof

This follows from the various estimates that we have, as follows:

(1) This follows from Proposition 4.25 (1), because:

[[math]] \begin{eqnarray*} \frac{r\sqrt{r}}{\sqrt{r}+\sqrt{N}} \lt 1 &\iff&r \lt 1+\sqrt{N/r}\\ &\iff&r(r-1)^2 \lt N \end{eqnarray*} [[/math]]

(2) This follows from Proposition 4.25 (2), because:

[[math]] \begin{eqnarray*} \frac{r^2c\sqrt{N}}{N-r^2} \lt 1 &\iff&N-r^2c\sqrt{N} \gt r^2\\ &\iff&(2\sqrt{N}-r^2c)^2 \gt r^4c^2+4r^2 \end{eqnarray*} [[/math]]

Indeed, this is equivalent to:

[[math]] \begin{eqnarray*} 2\sqrt{N} & \gt &r^2c+r\sqrt{r^2c^2+4}\\ &=&r(x+\sqrt{x^2+4}) \end{eqnarray*} [[/math]]

Here the value of [math]x[/math] is as follows:

[[math]] x =rc =r\left|\left|Pol(A)-\frac{A}{\sqrt{N}}\right|\right|_\infty [[/math]]

(3) This follows from Proposition 4.25 (3), because:

[[math]] \begin{eqnarray*} \frac{r^2(1+\sqrt N)}{N-r^2} \lt 1 &\iff&N-r^2\sqrt{N} \gt 2r^2\\ &\iff&(2\sqrt{N}-r^2)^2 \gt r^4+8r^2 \end{eqnarray*} [[/math]]

Indeed, this is equivalent to:

[[math]] 2\sqrt{N} \gt r^2+r\sqrt{r^2+8} [[/math]]

But this gives the result.

■

As a technical comment, for [math]A\in M_r(\pm1)[/math] Hadamard, Proposition 4.25 (2) gives:

[[math]] ||E||_\infty \leq\frac{r^2\sqrt{N}}{N-r^2}\left(\frac{1}{\sqrt{r}}-\frac{1}{\sqrt{N}}\right) =\frac{r\sqrt{r}N-r^2}{N-r^2} [[/math]]

Thus [math]||E||_\infty \lt 1[/math] for [math]N \gt r^3[/math], which is slightly weaker than Theorem 4.26 (1).

In view of the results above, it is convenient to make the following convention:

Definition

We denote by [math]\{x\}_{m \times n} \in M_{m \times n}(\mathbb R)[/math] the all-[math]x[/math] matrix, and by

[[math]] \begin{Bmatrix}x_{11}&\ldots&x_{1l}\\ \ldots&\ldots&\ldots\\ x_{k1}&\ldots&x_{kl}\end{Bmatrix}_{(m_1,\ldots,m_k) \times (n_1, \ldots, n_l)} [[/math]]

the matrix having all-[math]x_{ij}[/math] rectangular blocks [math]X_{ij}=\{x_{ij}\}_{m_i \times n_j} \in M_{m_i \times n_j}(\mathbb R)[/math], of prescribed size. In the case of square diagonal blocks, we simply write [math]\{x\}_n= \{x\}_{n \times n}[/math] and:

[[math]] \begin{Bmatrix}x_{11}&\ldots&x_{1k}\\ \ldots&\ldots&\ldots\\ x_{kk}&\ldots&x_{kk}\end{Bmatrix}_{n_1, \ldots n_k} = \begin{Bmatrix}x_{11}&\ldots&x_{1k}\\ \ldots&\ldots&\ldots\\ x_{k1}&\ldots&x_{kk}\end{Bmatrix}_{(n_1,\ldots,n_k) \times (n_1, \ldots, n_k)} [[/math]]

Modulo equivalence, the [math]\pm1[/math] matrices of size [math]r=1,2[/math] are as follows:

[[math]] \begin{pmatrix}+\end{pmatrix}_{(1)}\quad,\quad \begin{pmatrix}+&+\\+&-\end{pmatrix}_{(2)}\quad,\quad \begin{pmatrix}+&+\\+&+\end{pmatrix}_{(2')} [[/math]]

In the cases [math](1)[/math] and [math](2)[/math] above, where the matrix [math]A[/math] is invertible, the spectral properties of their complementary matrices are as follows:

Theorem

For the [math]N\times N[/math] Hadamard matrices of type

[[math]] \begin{pmatrix}+&+\\ +&D\end{pmatrix}_{(1)}\quad,\quad \begin{pmatrix} +&+&+&+\\ +&-&+&-\\ +&+&D_{00}&D_{01}\\ +&-&D_{10}&D_{11} \end{pmatrix}_{(2)} [[/math]]

the polar decomposition [math]D=UT[/math] with

[[math]] U=\frac{1}{\sqrt{N}}(D-E)\quad,\quad T=\sqrt{N}I-S [[/math]]

is given by the following formulae:

[[math]] E_{(1)}=\begin{Bmatrix}\frac{1}{1+\sqrt{N}}\end{Bmatrix}_{N-1}\quad,\quad E_{(2)}=\frac{2}{2+\sqrt{2N}}\begin{Bmatrix}1&1\\1&-1\end{Bmatrix}_{N/2-1,N/2-1} [[/math]]

[[math]] S_{(1)}=\begin{Bmatrix}\frac{1}{1+\sqrt{N}}\end{Bmatrix}_{N-1}\quad,\quad S_{(2)}=\frac{2}{\sqrt{2}+\sqrt{N}}\begin{Bmatrix}1&0\\0&1\end{Bmatrix}_{N/2-1,N/2-1} [[/math]]

In particular, all the matrices [math]D[/math] above are AHP.

Show Proof

For [math]A\in M_r(\pm1)[/math] Hadamard, the quantities in Definition 4.22 are:

[[math]] X_A=\frac{A^t}{r+\sqrt{rN}} [[/math]]

[[math]] Y_A=\frac{I_r}{\sqrt{r}+\sqrt{N}} [[/math]]

These formulae follow indeed from the following equalities:

[[math]] AA^t=A^tA=rI_r [[/math]]

[[math]] Pol(A)=A/\sqrt{r} [[/math]]

(1) Using the notation introduced in Definition 4.27, we have here:

[[math]] B_{(1)} = \{1\}_{1 \times N-1} [[/math]]

[[math]] C_{(1)} = B_{(1)}^t [[/math]]

Since the matrix [math]A_{(1)}=[+][/math] is Hadamard we have:

[[math]] X_{A_{(1)}}=Y_{A_{(1)}}=\frac{1}{1+\sqrt{N}} [[/math]]

We therefore obtain that:

[[math]] \begin{eqnarray*} E_{(1)} &=&\frac{1}{1+\sqrt{N}}\{1\}_{N-1 \times 1}[1]\{1\}_{1 \times N-1}\\ &=&\frac{1}{1+\sqrt{N}}\{1\}_{N-1} \end{eqnarray*} [[/math]]

Similarly, we obtain that:

[[math]] \begin{eqnarray*} S_{(1)} &=&\frac{1}{1+\sqrt{N}}\{1\}_{N-1 \times 1}\{1\}_{1 \times N-1}\\ &=&\frac{1}{1+\sqrt{N}}\{1\}_{N-1} \end{eqnarray*} [[/math]]

(2) Using the orthogonality of the first two rows of [math]H_{(2)}[/math], we find that the matrices [math]D_{00}[/math] and [math]D_{11}[/math] have size [math]N/2-1[/math]. Since since the matrix [math]A_{(2)}=[^+_+{\ }^+_-][/math] is Hadamard we have:

[[math]] X_{A_{(2)}}=\frac{A}{2+\sqrt{2N}} [[/math]]

[[math]] Y_{A_{(2)}}=\frac{I_2}{\sqrt{2}+\sqrt{N}} [[/math]]

But this gives the following formula:

[[math]] \begin{eqnarray*} &&E_{(2)}\\ &=&\frac{1}{2+\sqrt{2N}}\begin{Bmatrix}1&1\\1&-1\end{Bmatrix}_{(N/2-1,N/2-1) \times (1,1)}\begin{pmatrix}1&1\\1&-1\end{pmatrix}\begin{Bmatrix}1&1\\1&-1\end{Bmatrix}_{(1,1) \times (N/2-1,N/2-1)}\\ &=&\frac{2}{2+\sqrt{2N}}\begin{Bmatrix}1&1\\1&-1\end{Bmatrix}_{N/2-1,N/2-1} \end{eqnarray*} [[/math]]

Similarly, we obtain the following formula:

[[math]] \begin{eqnarray*} &&S_{(2)}\\ &=&\frac{1}{\sqrt{2}+\sqrt{N}}\begin{Bmatrix}1&1\\1&-1\end{Bmatrix}_{(N/2-1,N/2-1) \times (1,1)}\begin{Bmatrix}1&1\\1&-1\end{Bmatrix}_{(1,1) \times (N/2-1,N/2-1)}\\ &=&\frac{2}{\sqrt{2}+\sqrt{N}}\begin{Bmatrix}1&0\\0&1\end{Bmatrix}_{N/2-1,N/2-1} \end{eqnarray*} [[/math]]

Thus, we have obtained the formulae in the statement.

■

We refer to for more on all the above.

General references

Banica, Teo (2024). "Invitation to Hadamard matrices". arXiv:1910.06911 [math.CO].