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< \chi_i \left| \chi_i\right.\right>\tag{5}\label{selfoverlap}$$
This can now be expanded out using Eq. (\ref{AO}):
$$S_{ii} = \left< \sum_k c_{ik}\phi_k \left| \sum_j c_{ij}\phi_j\right.\right>\tag{5}$$
Now using the definition of the overlap-integral $S_{jk}=\left< \chi_j \left| \chi_k\right.\right>$ 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.