Prove that matrix is non-negative

Question

Problem:

Given $A_{1}, A_{2}, ..., A_{n}$ - finite sets and $a_{ij} = |A_{i}\cap A_{j}|$ - number of elements in intersection of sets. Prove, that matrix $(a_{ij})_{i=1,2,..,n}^{j=1,2,.., n}$ is non-negative.

I've cleared out that this matrix is symmetric and the largest elements are on its diagonal. I need to prove that $x^{T}Ax \ge 0$ or

$$\sum_{i=1}^n\sum_{j=1}^na_{ij}x_{i}x_{j} \ge 0$$

or its eigenvalues are non-negative.

I don't know, what need I do next? Any hint will be useful!

Answer 1

Let $\mathcal{A} = \cup_{i=1}^n A_i$ and $\chi_i : \mathcal{A} \to \mathbb{N}$ be the indicator function for $A_i, i = 1,\ldots n$.
For any $n$ real numbers $x_1, \ldots, x_n$, not all zero. Consider the function $f: \mathcal{A} \to \mathbb{R}$ defined by:

$$f(a) = \sum_{i=1}^{n} x_i \chi_i(a)$$

We have:

$$ \sum_{i=1}^{n}\sum_{j=1}^{n} a_{ij} x_i x_j = \sum_{i=1}^{n}\sum_{j=1}^{n} x_i x_j |A_i \cap A_j| = \sum_{i=1}^{n}\sum_{j=1}^{n} x_i x_j \left(\sum_{a\in A} \chi_i(a) \chi_j(a)\right)\\ = \sum_{a\in \mathcal{A}} \left(\sum_{i=1}^n x_i \chi_i(a)\right)\left(\sum_{j=1}^n x_j \chi_j(a)\right) = \sum_{a\in \mathcal{A}} f(a)^2 \ge 0 $$

Answer 2

A fun problem. I think that the following approach is natural (at least it is the first that occurred to me, YMMV).

Let us consider the union $$ A=\bigcup_{i=1}^nA_i. $$ I will work in the space $F_A$ of real valued functions from $A$ to $\mathbb{R}$. If you list the elements of $A$ like $$ A=\{a_1,a_2,\ldots,a_m\}, $$ you can identify the space $F_A$ with vectors of $\mathbb{R}^m$. The identification is natural. We identify the function $f:A\to\mathbb{R}$ with the vector $$ \vec{f}=(f(a_1),f(a_2),\ldots, f(a_m))\in\mathbb{R}^m. $$ Let us denote by $\chi_i$ the characteristic function of the subset $A_i$, that is the function in $F_A$ defined by $\chi_i(a)=1$, if $a\in A_i$, and $\chi_i(a)=0$, if $a\notin A_i$.

Let $x_i,i=1,2,\ldots,n$ be arbitrary real numbers as in your question. Consider the function $$ f=\sum_{i=1}^n x_i\chi_i\in F_A. $$ Let us look at the vector $\vec{f}\in\mathbb{R}^m$. I denote by $\langle\ ,\ \rangle$ the usual inner product of the space $\mathbb{R}^m$. We have trivially $$ \langle \vec{f},\vec{f}\rangle=\Vert\vec{f}\Vert^2\ge0. $$ On the other hand we have $$ \vec{f}=\sum_{i=1}^n x_i\vec{\chi_i}. $$ Bilinearity of the inner product gives us thus that $$ \langle\vec{f},\vec{f}\rangle=\sum_{i=1}^n\sum_{j=1}^n x_i x_j\langle\vec{\chi_i},\vec{\chi_j}\rangle. $$ But, more or less obviously (think about the inner product of two distinct vectors both with components zero or one only), we also have $$ \langle\vec{\chi_i},\vec{\chi_j}\rangle=|A_i\cap A_j|=a_{ij}. $$ The claim about non-negativity follows from this.

Answer 3

Hint:

• Claim: A symmetric matrix $X=(x_{ij})_{VV}$ (here $V=\{1,2,\ldots, k, \ldots, n\}$ ) is positive semidefinite if and only if all of its principal minors $det(x_{ij})_{UU}$ (here $\emptyset \neq U\subset V$) are nonnegative.

• Claim: A symmetric matrix $\begin{pmatrix}A& C^T\\ C& D\end{pmatrix}$ is positive semidefinite if and only if $D$ and $A - C^T D^{-1} C$ are positive semidefinite. In particular for $v\in\mathbb{R}^{n}$, $a \geq 0$ and $X_{n-1}\in\mathbb{R}^{(n-1)\times (n-1)}$ a symmetric matrix $\begin{pmatrix}a& v^T\\ v& X_{n-1}\end{pmatrix}$ is positive semidefinite if and only if $a$ and $a - v^T X_{n-1}^{-1} v$ are positive semidefinite.

For proofs see Meyer, Matrix Analysis and Applied Linear Algebra or Matrix Analysis by Roger A. Horn. Use induction on these facts to get the desired result.