Your question actually is one of the most important questions in analytic mechanics. This is because, when you explicitly write the Eulero-Lagrange equations for any constrained system with $n$ degrees of freedom and Lagrangian of the form:
$$L(t, {\bf q},\dot{\bf q}) = T(t, {\bf q},\dot{\bf q}) - U(t, {\bf q},\dot{\bf q})$$
where $T$ is quadratic in $\dot{\bf q}$ and $U$ is at most linear in $\dot{\bf q}$, you have a set of equations of the form:
$$\sum_{j=1}^n A(t, {\bf q})_{ij} \frac{d^2 q^j}{dt^2} = G_i\left(t, {\bf q},\frac{d q^j}{dt}\right)\quad i= 1,2,\ldots, n\:.\qquad (1)$$
As is known from the general theory of differential equations, if the system of differential equations can be re-written as:
$$ \frac{d^2 q^i}{dt^2} = \sum_{j=1}^n A^{-1}(t, {\bf q})_{ij} G_j\left(t, {\bf q},\frac{d q^j}{dt}\right)\quad i= 1,2,\ldots, n \qquad(2)\:.$$
that is in normal form (only the highest order derivative appears in the left-hand side), then the system admits a solution in a neighborhood of any fixed $t_0$ and it is uniquely determined by initial conditions
$$({\bf q}(t_0),\dot{\bf q}(t_0)) = ({\bf q}_0,\dot{\bf q}_0)\:.$$
Actually, it is true when the right-hand side of (2) is sufficiently regular:
$C^1$ jointly in all variables is OK (more weakly, continuity and the validity local Lipschitz condition in $({\bf q}_0,\dot{\bf q}_0)$ actually would also be enough). To pass from (1) to (2), it is necessary that $$\det A(t, {\bf q}) \neq 0\quad \mbox{everywhere in $(t, {\bf q})$.}$$
Let us show that, for a physical system of constrained material points, this condition is always verified under suitable hypotheses on the constraints.
Assume that the system is made of $N$, with $3N > n$, material points with masses $m_k>0$ and positions ${\bf r}_k$ in a given reference system. In this case the constraints are $c=3N-n$ requirements of the form:
$$f_l(t, {\bf r}_1, \ldots, {\bf r}_N)=0\quad l=1,2,\ldots, c \qquad (3)\:.$$
It is also assumed that the functions $f_l$ are sufficiently regular (for our computation $C^2$ is sufficient) and that the constraints are functionally independent. It means that, exactly on the set of points $(t, {\bf q})$ where (3) holds, it must also hold that the Jacobian matrix of elements (the 3N $x_k$ are all of the Cartesian components of all ${\bf r}_i$ labeled in any order, since it is not relevant here)
$$\frac{\partial f_l}{\partial x_k}$$
has $c$ linearly independent rows (or equivalently columns).
These requirements assure that the set of allowed positions is a $n=3N-c$ manifold for every time $t$ and that, locally, there are $n=3N-c$ free coordinates, $q^1,\ldots, q^2$, on that manifold and in a neighborhood of any fixed time $t$.
It is worth remarking that these $n$ coordinates can always picked out among the $3N$ coordinates $x_i$, even if this choice is not necessary.
As a consequence of the existence of $n$ local coordinates on the manifold of admissible configurations, the local relations hold: ${\bf r}_k={\bf r}_k(t,q^1,\ldots, q^n)$.
As you probably know, and the computation is straightforward, the matrix $A$ takes this form:
$$A_{ij} = \sum_{s=1}^N m_s \frac{\partial {\bf r}_s}{\partial q^i} \cdot \frac{\partial {\bf r}_s}{\partial q^j}\:.\qquad (4)$$
Now I wish to show that $\det A \neq 0$ when all the said hypotheses are true. It is obvious that it is sufficient to prove this fact only in one local coordinate system $q^1,\ldots, q^n$. Indeed, changing local coordinates and passing to the coordinates $Q^1,\ldots, Q^n$, we obtain a new matrix $A'$ related to the previous one by:
$$A'_{rs} = \sum_{i,j=1}^n\frac{\partial q^i}{\partial Q^r}\frac{\partial q^j}{\partial Q^s} A_{ij}\:.$$
Since the Jacobian matrix of elements $\frac{\partial q^i}{\partial Q^r}$ must be non singular, $\det A \neq 0$ is equivalent to $\det A' \neq 0$.
It is convenient to choose the free coordinates $q^1,\ldots, q^n$ as $n$ coordinates $x_k$ among the original components of the vectors ${\bf r}_j$ as said above.
For the sake of simplicity we can suppose that $q^1=x_1, q^2= x_2,\ldots , q^n = x_n$.
With this choice of the coordinates, assume that $\det A=0$. Consequently, there is a vector $v \in R^n -\{0\}$ such that $Av=0$ and, consequently,
$v^t A v =0$. Exploiting (4):
$$0=\sum_{ij}v_iA_{ij} v_j = \sum_{s=1}^N m_s \sum_{i,j}v_i\frac{\partial {\bf r}_s}{\partial q^i} \cdot v_j\frac{\partial {\bf r}_s}{\partial q^j}
= \sum_{s=1}^N m_s \left| \sum_{i}v_i\frac{\partial {\bf r}_s}{\partial q^i}\right|^2\:.$$
Since $m_s>0$, in turn it implies:
$$\sum_{i}v_i\frac{\partial {\bf r}_s}{\partial q^i} =0 \quad \mbox{for $r=1,2,\ldots, N$}\:.$$
Passing to the components of the ${\bf r}_s$:
$$\sum_{i}v_i\frac{\partial x_l}{\partial q^i} =0 \quad \mbox{for $l=1,2,\ldots, 3N$}\:.\quad (5)$$
Finally, remember that $x_l=q^l$, for $l=1,2, \ldots, n$. Choosing $l=1$, the requirements (5) produce:
$$v_1 =0$$
Choosing $l=2$, the requirements (5) produce:
$$v_2 =0$$
and so on. Finally we get $v=0$. This is not possible since $v \in R^n -\{0\}$. The existence of such $v$ was a consequence of $\det A=0$ that, consequently is untenable.