1
$\begingroup$

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?

$\endgroup$
2
+50
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.