Basis sets - negative contraction coefficients? I was looking through Basis Set Exchange when I noticed quite a few basis sets (STO-3G to STO-6G, for example) have negative contraction coefficients for some primitive Gaussians. As (based on what I know) the overlap between two STO-nG basis functions is equal to the sum of the overlap integrals between the pGTOs used to approximate the STO, this means that the diagonalised overlap matrix may have some negative elements. 

If this happens, what would the program do?
Diagonalization of a matrix means to find the eigenvalues of the matrix and put them into a diagonal matrix:

$$\mathbf{S}^\text{diag}=\mathrm{diag}\left( \lambda_1,...,\lambda_n \right)\tag{1}\label{diagmat}$$

for $\lambda_i$ being the eigenvalues of the matrix $\mathbf{S}$.
When we want to find the eigenvalues of the matrix $\mathbf{S}$ we solve an eigenvalue problem:

$$\mathbf{S}\mathbf{c}=\bar{\lambda}\mathbf{c}\tag{2}$$

for $\mathbf{c}$ being a matrix of the eigenvector, and $\bar{\lambda}$ being a vector of the eigenvalues.
This equation can also be written out in sum-form for the $i$the eigenvalue:

$$\sum_kS_{jk}c_{ik}=\lambda_ic_{ij}\tag{3}\label{eigproblem}$$

Now as you have stated we can define our atomic orbitals as a linear combination of primitive basis functions:

$$\chi_i=\sum_k c_{ik}\phi_k\tag{4}\label{AO}$$

This can be used to evaluate the self-overlap of the atomic orbitals:

$$S_{ii}=\int_\Omega\chi_i^*(\bar{r})\chi_i(\bar{r})\mathrm{d}\bar{r}=\int_\Omega\left|\chi_i(\bar{r})\right|^2\mathrm{d}\bar{r}=\left&lt; \chi_i \left| \chi_i\right.\right&gt;\tag{5}\label{selfoverlap}$$

This can now be expanded out using Eq. (\ref{AO}):

$$S_{ii} = \left&lt; \sum_k c_{ik}\phi_k \left| \sum_j c_{ij}\phi_j\right.\right&gt;\tag{5}$$

Now using the definition of the overlap-integral $S_{jk}=\left&lt; \chi_j \left| \chi_k\right.\right&gt;$ the above equation can be formulated as:

$$S_{ii}=\sum_{j,k}c_{ij}^*S_{jk}c_{ik}\tag{6}$$

Now using Eq. (\ref{eigproblem}) this can be expressed as:

$$S_{ii}=\sum_{j,k}c_{ij}^*\lambda_ic_{ij}=\lambda_i\sum_j\left|c_{ij}\right|^2\tag{7}$$

Now since $S_{ii}$ can be seen to be larger than or equal to zero from Eq. (\ref{selfoverlap}) and $\left|c_{ij}\right|^2$ must also be larger than or equal to zero, it follows that the eigenvalues $\lambda_i$ must all also be larger then or equal to zero.
I.e. from Eq. (\ref{diagmat}) the diagonalized overlap matrix cannot have any negative values.