Prove that matrix is non-negative 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! 
 A: 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
$$
A: 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.
A: 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.
