Show that a system of linear equations has a unique solution

linear algebrasystems of equations

Suppose that I have the following system of $K+1$ linear equations with $K\geq 3$
$$
\begin{cases}
\lambda_j\times \lambda_h'=\lambda'_j\times \lambda_h & \text{ for $K$ different pairs $(j,h)$ taken from $A$}\\
\lambda_1+…+\lambda_K=1
\end{cases}
$$

where

  • the unknowns are $(\lambda_1,…,\lambda_K)$

  • $(\lambda'_1,…,\lambda_K')$ are known parameters such that $$\lambda'_1+…+\lambda'_K=1$$

  • $\lambda_1>0,…,\lambda_K>0$ and $\lambda'_1>0,…,\lambda'_K>0$

  • $A\equiv \{(1,2),(1,3),…,(1,K),(2,K),(3,K),…,(K-1,K)\}$ with cardinality $2K-3$.

Question: could you help me to show that this system has a unique solution that is $$\lambda_1=\lambda'_1,…,\lambda_K=\lambda'_K$$

For example, when $K=5$, we have that $A\equiv \{(1,2),(1,3),(1,4),(1,5), (2,5),(3,5),(4,5)\}$ and a specification of the system could be
$$
\begin{cases}
\lambda_1\times \lambda_5'=\lambda'_1\times \lambda_5\\
\lambda_2\times \lambda_5'=\lambda'_2\times \lambda_5\\
\lambda_1\times \lambda_4'=\lambda'_1\times \lambda_4\\
\lambda_1\times \lambda_3'=\lambda'_1\times \lambda_3\\
\lambda_3\times \lambda_5'=\lambda'_3\times \lambda_5\\
\lambda_1+\lambda_2+\lambda_3+\lambda_4+\lambda_5=1
\end{cases}
$$

which implies
$$
\begin{cases}
\lambda_2=\lambda_1\times \frac{\lambda_2'}{\lambda_1'}\\
\lambda_3=\lambda_1\times \frac{\lambda_3'}{\lambda_1'}\\
\lambda_4=\lambda_1\times \frac{\lambda_4'}{\lambda_1'}\\
\lambda_5=\lambda_1\times \frac{\lambda_5'}{\lambda_1'}\\
\end{cases}
$$
Then, replacing this in $\lambda_1+\lambda_2+\lambda_3+\lambda_4+\lambda_5=1 $
we get
$$
\lambda_1\times \Big(\overbrace{1+\frac{\lambda_2'}{\lambda_1'}+ \frac{\lambda_3'}{\lambda_1'}+ \frac{\lambda_4'}{\lambda_1'}+ \frac{\lambda_5'}{\lambda_1'}}^{=1/\lambda_1'}\Big)=1
$$
which implies $\lambda_1=\lambda_1'$ and hence $\lambda_2=\lambda_2',\lambda_3=\lambda_3',\lambda_4=\lambda_4',\lambda_5=\lambda_5'$.

I am unable to generalise this procedure to any $K$ elements from the set $A$. Could you help?

Best Answer

This is not always true.

We can rewrite $\lambda_j\times \lambda_h'=\lambda'_j\times \lambda_h$ as $\frac{\lambda_j}{\lambda_j'} = \frac{\lambda_h}{\lambda_h'}$. If we can show from these $K$ equations that $$ \frac{\lambda_1}{\lambda_1'} = \frac{\lambda_2}{\lambda_2'} = \dots = \frac{\lambda_K}{\lambda_K'} $$ then there is a constant $C$ such that $\lambda_i = C \lambda_i'$ for all $i$; from knowing that $$\lambda_1 + \dots + \lambda_k = \lambda_1'+ \dots + \lambda_K'= 1,$$ we deduce that $C=1$ and therefore $\lambda_i = \lambda_i'$ for all $i$.

However, we cannot necessarily conclude that all the ratios $\frac{\lambda_j}{\lambda_j'}$ are equal. This depends on the $K$ specific equations we chose. Let $G$ be the graph with vertex set $\{1,\dots,K\}$ and an edge $hj$ whenever we choose the pair $(h,j)$ to form an equation. The requirement to have a unique solution is that $G$ must be connected. If so, for any $a,b \in \{1,\dots,K\}$ there is a path from $a$ to $b$ in $G$, and we get $\frac{\lambda_a}{\lambda_a'} = \dots = \frac{\lambda_b}{\lambda_b'}$ by transitivity along that path.

But here is an example (for $K=5$) without a unique solution. Choose the $5$ equations \begin{align} \lambda_1 \lambda_2' &= \lambda_1'\lambda_2 \\ \lambda_1 \lambda_3' &= \lambda_1'\lambda_3 \\ \lambda_1 \lambda_5' &= \lambda_1'\lambda_5 \\ \lambda_2 \lambda_5' &= \lambda_2'\lambda_5 \\ \lambda_3 \lambda_5' &= \lambda_3'\lambda_5 \ \end{align} Together, these equations are equivalent to $\frac{\lambda_1}{\lambda_1'} = \frac{\lambda_2}{\lambda_2'} = \frac{\lambda_3}{\lambda_3'} = \frac{\lambda_5}{\lambda_5'}$, but they leave out $\lambda_4$ entirely. So all $5$-tuples $\lambda$ with $$ (\lambda_1, \lambda_2, \lambda_3, \lambda_4, \lambda_5) = (A \lambda_1', A\lambda_2', A\lambda_3', B\lambda_4', A\lambda_5') $$ satisfy these $5$ equations, and if $A(\lambda_1'+\lambda_2'+\lambda_3'+\lambda_5') + B \lambda_4'= 1$, then $\lambda_1 + \dots + \lambda_5 = 1$ also holds. For any $0 < A < \frac{1}{\lambda_1'+\lambda_2'+\lambda_3'+\lambda_5'}$, we can set $B = \frac{1 - A(\lambda_1'+\lambda_2'+\lambda_3'+\lambda_5')}{\lambda_4'}$ and get a valid solution this way.

This is essentially the only kind of counterexample, though: cases where some variables are left out entirely. If every variable appears in at least one equation, then:

  1. For every $i = 2,\dots,K-1$, either $\lambda_1 \lambda_i' = \lambda_1'\lambda_i$ or $\lambda_i\lambda_K' = \lambda_i'\lambda_K$ is an equation, forcing $\frac{\lambda_i}{\lambda_i'}$ to be equal to either $\frac{\lambda_1}{\lambda_1'}$ or $\frac{\lambda_K}{\lambda_K'}$.
  2. To get $K$ equations, we need to either include both such equations for some $i$, or else include the equation $\lambda_1 \lambda_K' = \lambda_1'\lambda_K$. In either case, we can conclude that $\frac{\lambda_1}{\lambda_1'} = \frac{\lambda_K}{\lambda_K'}$. Therefore all $\frac{\lambda_i}{\lambda_i'}$ are equal.
Related Question