Quantifying how underdetermined a system of equations or optimization problem is In linear systems we have an exact solution when we have as many equations as unknowns and the equations are linearly independent, e.g.,
$$
x_0 + 2 x_1 = 5 \\
x_0 + 3 x_1 = 7 \\
$$
has the unique solution $x = (1, 2)$.
In many real-world cases we have underdetermined systems with more unknowns than equations, e.g.,
$$
x_0 + 2 x_1 + 3 x_2 + 4 x_3 = 5 \\
x_0 + 3 x_1 + 3 x_2 + 4 x_3 = 7 \\
$$
but we often impose some external cost function (e.g., maximum likelihood) to pick the best of the infinite number of solutions,
$$
x^* = \text{argmin}_x f(x).
$$
As a toy example, consider the squared loss function $f(x) = x_0^2 + x_1^2 + x_2^2 + x_3^2$. It gives the minimum-loss solution of $x^* = (1/26, 2, 3/26, 4/26)$.
Now consider adding the equation
$$
x_0 = 1/26 + 10^{-6}
$$
or alternatively the equation
$$
x_0^2 = 1/26^2
$$
Roughly speaking, neither of these equations really adds much information. Sure, they may change $x^*$ slightly, but not by much. These equations may add some information, but not enough to shift the parameters much or even produce a fully-determined system of equations.
In the general case, we have an underdetermined system of (potentially non-linear) equations subject to our minimum cost criterion $\text{argmin}_x f(x)$, but end up finding that in some sense, many of the rows of $A$ are degenerate, or nearly so, adding very little useful information to the minimization. Is there then some continuous metric (perhaps based in information theory) by which we can quantify the degeneracy or underdeterminedness of the matrix $A$, analogous to the number of linearly independent rows in the exact solution case?
 A: There is a metric that describes something that we could consider an underdeterminedness of a matrix - its Condition number. It describes how much the output is sensitive to changes in input and it can be e.g. used to discover multicollinearity in your data.
Assume you want to find $x$ given $A, b$:
$$
Ax = b
$$
Now, say that, because of some measurement error you measure $b + \Delta b$. This will have an effect of $x + \Delta x$ on your solution. We have:
$$
A(x + \Delta x) = (b + \Delta b) \implies Ax + A\Delta x = b + \Delta b \implies A\Delta x = \Delta b \implies \Delta x = A^{-1} \Delta b
$$
if $A^{-1}$ is invertible. Condition number is a maximum value a ratio of relative change in $x$ (i.e. $\frac{\Vert \Delta x \Vert}{\Vert x \Vert}$) and a relative change in $b$ (i.e. $\frac{\Vert \Delta b \Vert}{\Vert b \Vert}$):
$$
c = max \Bigl( \frac{\frac{\Vert \Delta x \Vert}{\Vert x \Vert}}{\frac{\Vert \Delta b \Vert}{\Vert b \Vert}} \Bigl)
$$
which you can prove to be equal to $c = \Vert A \Vert \Vert A^{-1} \Vert$ (where $\Vert \cdot \Vert$ denotes Euclidean $L^2$ norm)
