IMO 1965 Problem 2

Proposed by: -
Verified: yes
Verdicts: PASS + PASS
Solve time: 5m48s

Problem

Consider the system of equations $$ a_{11}x_1 + a_{12}x_2 + a_{13}x_3 = 0 $$ $$ a_{21}x_1 + a_{22}x_2 + a_{23}x_3 = 0 $$ $$ a_{31}x_1 + a_{32}x_2 + a_{33}x_3 = 0 $$ with unknowns $x_1$, $x_2$, $x_3$. The coefficients satisfy the conditions:

(a) $a_{11}$, $a_{22}$, $a_{33}$ are positive numbers;

(b) the remaining coefficients are negative numbers;

Prove that the given system has only the solution $x_1 = x_2 = x_3 = 0$.

Exploration

The coefficient matrix has positive diagonal entries and negative off-diagonal entries. The condition that the sum of the coefficients in each row is positive means that for each row,

$$a_{ii}+\sum_{j\ne i}a_{ij}>0.$$

Since the off-diagonal coefficients are negative, this implies

$$a_{ii}>\sum_{j\ne i}|a_{ij}|.$$

Thus each diagonal entry exceeds the sum of the absolute values of the other entries in its row. This is a strict diagonal dominance condition.

A first idea is to prove that the determinant is nonzero from diagonal dominance. That would solve the problem immediately. However, invoking a general theorem about diagonally dominant matrices would require proving that theorem. There is a more direct argument.

Suppose a nonzero solution exists. Choose an index $k$ for which $|x_k|$ is maximal among $|x_1|,|x_2|,|x_3|$. Looking at the $k$-th equation,

$$a_{kk}x_k=-\sum_{j\ne k}a_{kj}x_j.$$

Taking absolute values gives

$$a_{kk}|x_k| \le \sum_{j\ne k}|a_{kj}|,|x_j| \le \Bigl(\sum_{j\ne k}|a_{kj}|\Bigr)|x_k|.$$

If $x_k\neq0$, this yields

$$a_{kk}\le \sum_{j\ne k}|a_{kj}|,$$

contradicting strict diagonal dominance.

The only delicate point is deriving strict diagonal dominance from the positivity of the row sums. Since the off-diagonal entries are negative, one must rewrite them using absolute values carefully.

This approach avoids any determinant computation and uses only the given hypotheses.

Problem Understanding

We are given a homogeneous system of three linear equations in three unknowns. The diagonal coefficients are positive, every off-diagonal coefficient is negative, and the sum of the coefficients in each row is positive.

The task is to prove that the homogeneous system admits no nonzero solution. Equivalently, we must prove that the coefficient matrix is nonsingular.

This is a Type B problem. The statement to be established is that the only solution is

$$x_1=x_2=x_3=0.$$

The main difficulty is that no explicit information about the determinant is given. A direct computation of the determinant is impossible because the coefficients are arbitrary. The key observation is that the sign conditions and the positivity of each row sum imply strict diagonal dominance, and that property is strong enough to exclude nonzero solutions.

Proof Architecture

We shall prove two lemmas.

Lemma 1. For each row $i$,

$$a_{ii}>\sum_{j\ne i}|a_{ij}|.$$

Sketch. The row sum is positive, the diagonal entry is positive, and every off-diagonal entry is negative. Rewriting the row sum in terms of absolute values yields the inequality.

Lemma 2. If a homogeneous linear system has a nonzero solution and its coefficient matrix satisfies

$$a_{ii}>\sum_{j\ne i}|a_{ij}|$$

for every row, then a contradiction arises.

Sketch. Choose a component of maximal absolute value among the coordinates of a nonzero solution. Apply the corresponding equation and the triangle inequality to obtain the reverse inequality

$$a_{ii}\le \sum_{j\ne i}|a_{ij}|,$$

contradicting strict diagonal dominance.

The second lemma is the critical step. A careless argument might overlook the need to choose a coordinate of maximal absolute value before applying the triangle inequality.

Solution

Lemma 1

For each $i\in{1,2,3}$,

$$a_{ii}>\sum_{j\ne i}|a_{ij}|.$$

Proof

Fix $i\in{1,2,3}$.

By hypothesis, the sum of the coefficients in the $i$-th equation is positive:

$$a_{ii}+\sum_{j\ne i}a_{ij}>0.$$

Every coefficient $a_{ij}$ with $j\ne i$ is negative. Hence

$$a_{ij}=-|a_{ij}|$$

for all $j\ne i$. Substituting into the preceding inequality gives

$$a_{ii}-\sum_{j\ne i}|a_{ij}|>0.$$

Therefore

$$a_{ii}>\sum_{j\ne i}|a_{ij}|.$$

This proves the lemma. ∎

Certification. This step establishes strict diagonal dominance of every row; replacing the negative off-diagonal entries by their absolute values is indispensable because the row-sum condition alone does not immediately have the required form.

Lemma 2

The homogeneous system

$$\sum_{j=1}^{3}a_{ij}x_j=0, \qquad i=1,2,3,$$

has no nonzero solution if

$$a_{ii}>\sum_{j\ne i}|a_{ij}|$$

for every $i$.

Proof

Assume, seeking a contradiction, that there exists a nonzero solution

$$(x_1,x_2,x_3).$$

Among the numbers $|x_1|,|x_2|,|x_3|$, choose one of maximal value. Let its index be $k$. Then

$$|x_k|\ge |x_j|$$

for all $j$.

Since the solution is nonzero, $x_k\neq0$.

The $k$-th equation is

$$a_{kk}x_k+\sum_{j\ne k}a_{kj}x_j=0.$$

Rearranging,

$$a_{kk}x_k=-\sum_{j\ne k}a_{kj}x_j.$$

Taking absolute values and applying the triangle inequality,

$$a_{kk}|x_k| = \left|\sum_{j\ne k}a_{kj}x_j\right| \le \sum_{j\ne k}|a_{kj}|,|x_j|.$$

Because $|x_j|\le |x_k|$ for every $j$,

$$a_{kk}|x_k| \le \left(\sum_{j\ne k}|a_{kj}|\right)|x_k|.$$

Since $x_k\neq0$, division by $|x_k|$ yields

$$a_{kk}\le \sum_{j\ne k}|a_{kj}|.$$

This contradicts the assumed strict inequality

$$a_{kk}>\sum_{j\ne k}|a_{kj}|.$$

The contradiction shows that no nonzero solution exists. ∎

Certification. This step establishes that strict diagonal dominance excludes every nonzero solution; choosing a coordinate of maximal absolute value is essential because otherwise the comparison with $|x_k|$ would be unjustified.

Combining Lemma 1 and Lemma 2, the given system admits no nonzero solution. Hence the only solution is

$$x_1=x_2=x_3=0.$$

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the deduction of strict diagonal dominance. Starting from

$$a_{ii}+\sum_{j\ne i}a_{ij}>0,$$

and using $a_{ij}<0$ for $j\ne i$, one obtains

$$a_{ij}=-|a_{ij}|.$$

Substitution gives

$$a_{ii}-\sum_{j\ne i}|a_{ij}|>0.$$

No weaker conclusion is possible. A careless argument that merely states $a_{ii}>0$ would lose the quantitative information needed later.

The second delicate step is the choice of the maximal component. Let $k$ satisfy

$$|x_k|=\max{|x_1|,|x_2|,|x_3|}.$$

Then

$$|a_{kj}x_j| \le |a_{kj}|,|x_k|$$

for every $j\ne k$. Summing these inequalities yields

$$\sum_{j\ne k}|a_{kj}|,|x_j| \le \left(\sum_{j\ne k}|a_{kj}|\right)|x_k|.$$

Without maximality, this estimate could fail, and the contradiction would not follow.

The third delicate point is dividing by $|x_k|$. This is valid because the solution was assumed nonzero and $k$ was chosen so that $|x_k|$ is maximal. If $|x_k|=0$, then every $|x_j|=0$, contradicting the assumption that the solution is nonzero.

Alternative Approaches

A different proof uses determinants. Lemma 1 shows that the matrix is strictly diagonally dominant by rows. One may then prove the theorem that every strictly diagonally dominant matrix is nonsingular. Applying that theorem immediately implies that the determinant of the coefficient matrix is nonzero, so the homogeneous system has only the trivial solution.

Another approach proceeds by contradiction using the largest and smallest coordinates separately. Let $x_k$ be a component with maximal value and $x_m$ a component with minimal value. The sign pattern of the coefficients allows one to derive incompatible inequalities for $x_k$ and $x_m$ from the corresponding equations. This method also exploits the positivity of the row sums, but it requires more case analysis than the maximal absolute value argument and is therefore less economical.