Prove that matrix is non-negative

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 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.