Suppose you have a differential equation with n distinct functions of $t$ where
$\frac{d^2x_1}{dt^2}=k_{11}x_1+...k_{1n}x_n$
.
.
.
$\frac{d^2x_n}{dt^2}=k_{n1}x_1+...k_{nn}x_n$
I want to show that any set of solutions of this differential equation $(x_1,x_2,...,x_n) $
can be written as a linear combination of solutions of the form $(e^{iw_1t},...,e^{iw_1t}), (e^{iw_2t},...e^{iw_2t}), ...,(e^{iw_mt},...e^{iw_mt})$ where each $w_j$ is a real number.
i.e. I want to know why the motion of any oscillator can be written as a linear combination of its normal modes. I would also appreciate it if you could tell me if a proof of this fact has to do with eigenvalues and eigenvectors in general.
The system of differential equations you wrote could be written as,
$$ \frac{d^2}{dt^2} \left[\begin{array}{c} x_1 \\ \vdots \\ x_n \end{array}\right] = \left[\begin{array}{ccc} k_{11} & \cdots & k_{1n} \\ \vdots & \ddots & \vdots \\ k_{1n} & \cdots & k_{nn} \end{array}\right] \left[ \begin{array}{c} x_1 \\ \vdots \\ x_n\end{array}\right]$$
$$ \frac{d^2}{dt^2} \vec{x} = K \vec{x}$$
The matrix $K=[k_{ij}]$ acts on the indices of the functions $x_1,\dots,x_n$.
We will suppose that $K$ is diagonalizable with eigenvalues $\lambda_1, \dots, \lambda_n$.
Let $\Lambda$ be the diagonal form of $K$.
Let $V$ be the matrix of eigenvectors of $K$. Note that $\Lambda = V^{-1} K V$.
We can now write the system of differential equations as,
$$ \frac{d^2}{dt^2} \vec{x} = V \Lambda V^{-1} \vec{x} $$
$$ V^{-1}\frac{d^2}{dt^2} \vec{x} = \Lambda V^{-1} \vec{x} $$
$$ \frac{d^2}{dt^2} V^{-1}\vec{x} = \Lambda V^{-1} \vec{x} $$
Let $\vec{y} = V^{-1} \vec{x}$, then we have $ \frac{d^2}{dt^2} \vec{y} = \Lambda \vec{y} $. This corresponds to the following system of equations.
$$ \frac{d^2 y_1}{dt^2} = \lambda_1 y_1 $$ $$ \frac{d^2 y_2}{dt^2} = \lambda_2 y_2 $$ $$ \vdots $$ $$ \frac{d^2 y_n}{dt^2} = \lambda_n y_n $$
Clearly the solutions are of the form,
$$y_j(t) = C_1 e^{\sqrt{\lambda_j}\ t} + C_2 e^{-\sqrt{\lambda_j}\ t},$$
to obtain the $x_j$'s we just multiply by the $V$ matrix.
$$ x_j(t) = \sum_i V_{ji} y_i(t)$$
Whether or not the solutions are oscillators depends on whether the eigenvalues are positive, negative, or complex. In physical applications it wouldn't be uncommon for $K$ to be a symmetric matrix with negative eigenvalues.