Return to Answer

Here's something which shows the constructions yielding $2n$ are almost tight.

Let $A$ be the $|U| \times n$ matrix where the entry $a_{ij}$ is equal to $1$ if $i \in S_j$ and $-1$ otherwise, and let $B=A^T A$.

Then $B$ is an $n \times n$ matrix having diagonal entries equal to $|U|$ and off-diagonal entries equal to $$b_{ij}=|U| - 2 (|S_j \cap S_i^C| + |S_i \cap S_j^C|)$$ $$=|U|-4(n- |S_i \cap S_j| ) \leq |U| - 2n.$$

Letting $x$ be the $n \times 1$ vector of $1$'s, we have by direct computation $$(Ax)^T(Ax) =n (|U| -2n)^2$$ Conversely, by the above we have $$(Ax)^T (Ax) = \sum_i \sum_j b_{ij} = n |U| + \sum_{(i,j), i \neq j} b_{ij} \leq n|U| + n(n-1) (|U|-2n)$$

Comparing, we have $(|U|-2n)^2 \leq |U|+(n-1) (|U|-2n)$. Since $|U|$ is an integer, this implies $|U| \geq 2n-1$ (if $|U| \leq 2n-2$ the right side is non-positive while the left side is positive).

Edited to add: In the case where $n$ is odd, this can be improved slightly, since we actually have $|S_i \cap S_j| \leq \frac{n-1}{2}$. After making this change, the final inequality changes to $(U-2n)^2 \leq |U| + (n-1) (|U|-2n-2)$, which implies $|U| \geq 2n$. This matches the conjectured bound of Gerhard's comment and Padraig's answer.

Note: The original answer here had (as noted in the comments) an incorrect calculation of $(Ax)^T Ax$. I've replaced it by the trivial bound $(Ax)^T Ax \geq 0$, which weakens the bound to it doesn't quite match the Hadamard bound anymore.

Here's something which shows the constructions yielding $2n$ are almost tight.

Let $A$ be the $|U| \times n$ matrix where the entry $a_{ij}$ is equal to $1$ if $i \in S_j$ and $-1$ otherwise, and let $B=A^T A$.

Then $B$ is an $n \times n$ matrix having diagonal entries equal to $|U|$ and off-diagonal entries equal to $$b_{ij}=|U| - 2 (|S_j \cap S_i^C| + |S_i \cap S_j^C|)$$ $$=|U|-4(n- |S_i \cap S_j| ) \leq |U| - 2n.$$

Letting $x$ be the $n \times 1$ vector of $1$'s, this implies
$$(Ax)^T (Ax) = \sum_i \sum_j b_{ij} = n |U| + \sum_{(i,j), i \neq j} b_{ij} \leq n|U| + n(n-1) (|U|-2n).$$

But this must be at least $0$, which implies $|U| \geq 2n-2$.

If $n$ is odd, we can improve this slightly to $2n-1$ by replacing the bound $|S_i \cap S_j| \leq n/2$ by $|S_i \cap S_j| \leq (n-1)/2$.

Here's something which shows the constructions yielding $2n$ are almost tight.

Let $A$ be the $|U| \times n$ matrix where the entry $a_{ij}$ is equal to $1$ if $i \in S_j$ and $-1$ otherwise, and let $B=A^T A$.

Then $B$ is an $n \times n$ matrix having diagonal entries equal to $|U|$ and off-diagonal entries equal to $$b_{ij}=|U| - 2 (|S_j \cap S_i^C| + |S_i \cap S_j^C|)$$ $$=|U|-4(n- |S_i \cap S_j| ) \leq |U| - 2n.$$

Letting $x$ be the $n \times 1$ vector of $1$'s, we have by direct computation $$(Ax)^T(Ax) =n (|U| -2n)^2$$ Conversely, by the above we have $$(Ax)^T (Ax) = \sum_i \sum_j b_{ij} = n |U| + \sum_{(i,j), i \neq j} b_{ij} \leq n|U| + n(n-1) (|U|-2n)$$

Comparing, we have $(|U|-2n)^2 \leq |U|+(n-1) (|U|-2n)$. Since $|U|$ is an integer, this implies $|U| \geq 2n-1$ (if $|U| \leq 2n-2$ the right side is non-positive while the left side is positive).

Edited to add: In the case where $n$ is odd, this can be improved slightly, since we actually have $|S_i \cap S_j| \leq \frac{n-1}{2}$. After making this change, the final inequality changes to $(U-2n)^2 \leq |U| + (n-1) (|U|-2n-2)$, which implies $|U| \geq 2n$. This matches the conjectured bound of Gerhard.

Here's something which shows the constructions yielding $2n$ are almost tight.

Let $A$ be the $|U| \times n$ matrix where the entry $a_{ij}$ is equal to $1$ if $i \in S_j$ and $-1$ otherwise, and let $B=A^T A$.

Then $B$ is an $n \times n$ matrix having diagonal entries equal to $|U|$ and off-diagonal entries equal to $$b_{ij}=|U| - 2 (|S_j \cap S_i^C| + |S_i \cap S_j^C|)$$ $$=|U|-4(n- |S_i \cap S_j| ) \leq |U| - 2n.$$

Letting $x$ be the $n \times 1$ vector of $1$'s, we have by direct computation $$(Ax)^T(Ax) =n (|U| -2n)^2$$ Conversely, by the above we have $$(Ax)^T (Ax) = \sum_i \sum_j b_{ij} = n |U| + \sum_{(i,j), i \neq j} b_{ij} \leq n|U| + n(n-1) (|U|-2n)$$

Comparing, we have $(|U|-2n)^2 \leq |U|+(n-1) (|U|-2n)$. Since $|U|$ is an integer, this implies $|U| \geq 2n-1$ (if $|U| \leq 2n-2$ the right side is non-positive while the left side is positive).

Edited to add: In the case where $n$ is odd, this can be improved slightly, since we actually have $|S_i \cap S_j| \leq \frac{n-1}{2}$. After making this change, the final inequality changes to $(U-2n)^2 \leq |U| + (n-1) (|U|-2n-2)$, which implies $|U| \geq 2n$. This matches the conjectured bound of Gerhard's comment and Padraig's answer.

Here's something which shows the constructions yielding $2n$ are almost tight.

Let $A$ be the $|U| \times n$ matrix where the entry $a_{ij}$ is equal to $1$ if $i \in S_j$ and $-1$ otherwise, and let $B=A^T A$.

Then $B$ is an $n \times n$ matrix having diagonal entries equal to $|U|$ and off-diagonal entries equal to $$b_{ij}=|U| - 2 (|S_j \cap S_i^C| + |S_i \cap S_j^C|)$$ $$=|U|-4(n- |S_i \cap S_j| ) \leq |U| - 2n.$$

Letting $x$ be the $n \times 1$ vector of $1$'s, we have by direct computation $$(Ax)^T(Ax) =n (|U| -2n)^2$$ Conversely, by the above we have $$(Ax)^T (Ax) = \sum_i \sum_j b_{ij} = n |U| + \sum_{(i,j), i \neq j} b_{ij} \leq n|U| + n(n-1) (|U|-2n)$$

Comparing, we have $(|U|-2n)^2 \leq |U|+(n-1) (|U|-2n)$. Since $|U|$ is an integer, this implies $|U| \geq 2n-1$ (if $|U| \leq 2n-2$ the right side is non-positive while the left side is positive).

Here's something which shows the constructions yielding $2n$ are almost tight.

Let $A$ be the $|U| \times n$ matrix where the entry $a_{ij}$ is equal to $1$ if $i \in S_j$ and $-1$ otherwise, and let $B=A^T A$.

Then $B$ is an $n \times n$ matrix having diagonal entries equal to $|U|$ and off-diagonal entries equal to $$b_{ij}=|U| - 2 (|S_j \cap S_i^C| + |S_i \cap S_j^C|)$$ $$=|U|-4(n- |S_i \cap S_j| ) \leq |U| - 2n.$$

Letting $x$ be the $n \times 1$ vector of $1$'s, we have by direct computation $$(Ax)^T(Ax) =n (|U| -2n)^2$$ Conversely, by the above we have $$(Ax)^T (Ax) = \sum_i \sum_j b_{ij} = n |U| + \sum_{(i,j), i \neq j} b_{ij} \leq n|U| + n(n-1) (|U|-2n)$$

Comparing, we have $(|U|-2n)^2 \leq |U|+(n-1) (|U|-2n)$. Since $|U|$ is an integer, this implies $|U| \geq 2n-1$ (if $|U| \leq 2n-2$ the right side is non-positive while the left side is positive).

Edited to add: In the case where $n$ is odd, this can be improved slightly, since we actually have $|S_i \cap S_j| \leq \frac{n-1}{2}$. After making this change, the final inequality changes to $(U-2n)^2 \leq |U| + (n-1) (|U|-2n-2)$, which implies $|U| \geq 2n$. This matches the conjectured bound of Gerhard.