Posted in Olympiad exercises, Số học - tổ hợp

Sylvester’s Problem, Gallai’s Solution

(Để tạm đây)


The Sylvester Problem has been posed by James Joseph Sylvester in 1893 in Educational Times:

Let n given points have the property that the line joining any two of them passes through a third point of the set. Must the n points all lie on one line?

T. Gallai’s proof has been outlined by P. Erdös in his submission of the problem to The American Mathematical Monthly in 1943.


Given the set Π of noncollinear points, consider the set of lines Σ that pass through at least two points of Π. Such lines are said to be connecting. Among the connecting lines, those that pass through exactly two points of Π are called ordinary.

Choose any point p1Π. If p1 lies on an ordinary line we are done, so we may assume that p1 lies on no ordinary line. Project p1 to infinity and consider the set of connecting lines containing p1. These lines are all parallel to each other, and each contains p1 and at least two other points of Π. Any connecting line not through p1 forms an angle with the parallel lines; let s be a connecting line (not through p1) which forms the smallest such angle:


Then s must be ordinary! For suppose s were to contain three (or more) points of Π, say, p2, p3, p4 named so that p3 is between p2 and p4:


The connecting line through p3 and p1 (being not ordinary) would contain a third point of Π, say p5, and now either the line p2p5 or the line p4p5 would form a smaller angle with the parallel lines than does s.


  1. P. Borwein, W. O. J. Moser, A survey of Sylvester’s problem and its generalizations, Aequationes Mathematicae 40 (1990) 111 – 135
  2. P. Erdös, R. Steinberg, Problem 4065 [1943, 65], The American Mathematical Monthly, Vol. 51, No. 3 (Mar., 1944), pp. 169-171
  3. J. J. Sylvester, Educational Times, Mathematical Question 11851, vol. 59 (1893), p. 98
Posted in Olympiad exercises

Trace of powers of a nilpotent matrix

File: Trace of powers of a nilpotent matrix

This note, I copied from Yoshi on MathStackExchange:

Let {A} be an {n\times n} complex nilpotent matrix. Then we know that because all eigenvalues of {A} must be 0, it follows that {\text{tr}(A^n)=0} for all positive integers {n}.

What I would like to show is the converse, that is, if {\text{tr}(A^n)=0} for all positive integers {n}, then {A} is nilpotent. I tried to show that 0 must be an eigenvalue of {A}, then try to show that all other eigenvalues must be equal to 0. However, I am stuck at the point where I need to show that {\det(A)=0}.

May I know of the approach to show that {A} is nilpotent?

The answer of Alvarez:

If the eigenvalues of {A} are {\lambda_1}, {\dots}, {\lambda_n}, then the eigenvalues of {A^k} are {\lambda_1^k}, {\dots}, {\lambda_n^k}. It follows that if all powers of {A} have zero trace, then {\lambda_1^k+\dots+\lambda_n^k=0, \forall k\geq 1}.

Using [Newton’s identities] to express the elementary symmetric functions of the {\lambda_i}‘s in terms of their power sums, we see that all the coefficients of the characteristic polynomial of {A} (except that of greatest degree, of course) are zero. This means that {A} is nilpotent.
The answer of JBC:

Assume that for all {k=1,\ldots,n}, {\mathrm{tr}(A^k) = 0} where {A} is a {n\times n} matrix. We consider the eigenvalues in {\mathbb{C}}.

Suppose {A} is not nilpotent, so {A} has some non-zero eigenvalues {\lambda_1,\ldots,\lambda_r}.
Let {n_i} the multiplicity of {\lambda_i} then

\displaystyle \left\{\begin{array}{ccc}n_1\lambda_1+\cdots+n_r\lambda_r&=&0 \\ \vdots & & \vdots \\ n_1\lambda_1^r+\cdots+n_r\lambda_r^r&=&0\end{array}\right.

So we have

\displaystyle \left(\begin{array}{cccc}\lambda_1&\lambda_2&\cdots&\lambda_r\\\lambda_1^2 & \lambda_2^2 & \cdots & \lambda_r^2 \\ \vdots & \vdots & \vdots & \vdots \\ \lambda_1^r & \lambda_2^r & \cdots & \lambda_r^r\end{array}\right)\left(\begin{array}{c}n_1 \\ n_2 \\ \vdots \\ n_r \end{array}\right)=\left(\begin{array}{c}0 \\ 0\\ \vdots \\ 0\end{array}\right)


\displaystyle \mathrm{det}\left(\begin{array}{cccc}\lambda_1&\lambda_2&\cdots&\lambda_r\\\lambda_1^2 & \lambda_2^2 & \cdots & \lambda_r^2 \\ \vdots & \vdots & \vdots & \vdots \\ \lambda_1^r & \lambda_2^r & \cdots & \lambda_r^r\end{array}\right)=\lambda_1\cdots\lambda_r\,\mathrm{det}\left(\begin{array}{cccc} 1 & 1 & \cdots & 1 \\ \lambda_1&\lambda_2&\cdots&\lambda_r\\\lambda_1^2 & \lambda_2^2 & \cdots & \lambda_r^2 \\ \vdots & \vdots & \vdots & \vdots \\ \lambda_1^{r-1} & \lambda_2^{r-1} & \cdots & \lambda_r^{r-1}\end{array}\right)\neq 0


So the system has a unique solution which is {n_1=\ldots=n_r=0}. Contradiction.
The answer of Qiaochu Yuan: Here is an argument that does not involve Newton’s identities, although it is still closely related to symmetric functions. Write

\displaystyle f(z) = \sum_{k\ge 0} z^k \text{tr}(A^k) = \sum_{i=1}^n \frac{1}{1 - z \lambda_i}

where {\lambda_i} are the eigenvalues of {A}. As a meromorphic function, {f(z)} has poles at the reciprocals of all of the nonzero eigenvalues of {A}. Hence if {f(z) = n} identically, then there are no such nonzero eigenvalues.

The argument using Newton’s identities, however, proves the stronger statement that we only need to require {\text{tr}(A^k) = 0} for {1 \le k \le n}. Newton’s identities are in fact equivalent to the identity

\displaystyle f(z) = n - \frac{z p'(z)}{p(z)}

where {p(z) = \prod_{i=1}^n (1 - z \lambda_i)}. To prove this identity it suffices to observe that

\displaystyle \log p(z) = \sum_{i=1}^n \log (1 - z \lambda_i)

and differentiating both sides gives

\displaystyle \frac{p'(z)}{p(z)} = \sum_{i=1}^n \frac{- \lambda_i}{1 - z \lambda_i}.

(The argument using Newton’s identities is also valid over any field of characteristic zero.)