Solving an olympiad-type maximization problem via linear algebra

When I first delved in the world of contest math, a topic which I particularly had problems with (and still do today) was optimization. Besides memorizing various inequalities, it was also hard for me to transform such problems into a form where these inequalities can be used.

Hence I was quite anxious to solve a problem introduced to me by a friend yesterday which is as follows.

Problem

Find the maximum value of

$$\frac{ab+bc+cd}{a^2+b^2+c^2+d^2}$$

where $(a,b,c,d)\in {\mathbb{R}}^4\setminus \{(0,0,0,0)\}$.

Solution via inequalities

What I think is peculiar with this problem is the numerator, since it seems to lack "symmetry". To explain, $b$ and $c$ appear twice while $a$ and $d$ appear only once, hence their effects on the value of the expression will be different.

My friend used the arithmetic mean - geometric mean (AM-GM) inequality to solve this problem. It involved some complicated ways of seeking the appropriate coefficients which may take too long to explain, so I will just show the core of his solution.

Let $t\in \mathbb{R}$, where $t>1$. Using AM-GM, we obtain

$$\begin{array}{rlrlrl}{t}^2{a}^2+b^2& \ge 2tab& ⟺& & ab& \le \frac{t}{2}{a}^2+\frac{1}{2t}{b}^2\\ (t^2-1)b^2+(t^2-1)c^2& \ge 2(t^2-1)bc& ⟺& & bc& \le \frac{1}{2}{b}^2+\frac{1}{2}{c}^2\\ c^2+t^2{d}^2& \ge 2tcd& ⟺& & cd& \le \frac{1}{2t}{c}^2+\frac{t}{2}{d}^2\end{array}$$

Taking the sum of the inequalities in the right side, we obtain

$$ab+bc+cd\le \frac{t}{2}{a}^2+(\frac{1}{2t}+\frac{1}{2})b^2+(\frac{1}{2t}+\frac{1}{2})c^2+\frac{t}{2}{d}^2$$

Now, if we force $t$ to satisfy ${\displaystyle \frac{t}{2}}={\displaystyle \frac{1}{2t}}+{\displaystyle \frac{1}{2}}$, then the only possible value for $t$ that satisfies the imposed conditions is $t={\displaystyle \frac{1+\sqrt{5}}{2}}$. This would imply

$$\frac{ab+bc+cd}{a^2+b^2+c^2+d^2}\le \frac{1+\sqrt{5}}{4}$$

This upper bound is attainable for values of $a,b,c,d$ satisfying $\left({\displaystyle \frac{1+\sqrt{5}}{4}}\right)a=b$, $b=c$, and $c=\left({\displaystyle \frac{1+\sqrt{5}}{4}}\right)d$, which follows from the equality condition of AM-GM. Hence $\boxed{{\displaystyle {\displaystyle \frac{1+\sqrt{5}}{4}}}}$ is the maximum value.

Another perspective via linear algebra

As I have remarked before, the problem I have with olympiad-type optimization problems is the difficulty in manipulating the objective function into a suitable form to perform inequalities on. For instance, the solution I have shown above does not show the tedious reason why the coefficients are to be written in such a way as function of $t$, but it is necessary in order to use the appropriate inequality.

Hence, I sought to find another way of solving the problem. One may observe that the numerator seems to appear like a dot product. Furthermore the denominator appears to be the squared Euclidean norm of the vector $(a,b,c,d)$. It may then be fruitful to ask this question: can we view the problem in terms of linear algebra?

Let $(a,b,c,d)\in {\mathbb{R}}^4\setminus \{(0,0,0,0)\}$. Observe that we may rewrite the expression as follows.

$$\begin{array}{rl}\frac{ab+bc+cd}{a^2+b^2+c^2+d^2}& =\frac{1}{2}\frac{a(b)+b(a+c)+c(b+d)+d(c)}{a^2+b^2+c^2+d^2}\\ & =\frac{1}{2}\frac{\left[\begin{array}{cccc}a& b& c& d\end{array}\right]\cdot \left[\begin{array}{cccc}0& 1& 0& 0\\ 1& 0& 1& 0\\ 0& 1& 0& 1\\ 0& 0& 1& 0\end{array}\right]\left[\begin{array}{c}a\\ b\\ c\\ d\end{array}\right]}{\left[\begin{array}{cccc}a& b& c& d\end{array}\right]\cdot \left[\begin{array}{c}a\\ b\\ c\\ d\end{array}\right]}\end{array}$$

We can therefore view the problem as follows.

Find the maximum value of

$$\frac{1}{2}\frac{v^{T}Mv}{v^{T}v}$$

where $v\in {\mathbb{R}}^4\setminus \{(0,0,0,0)\}$ and $M=\left[\begin{array}{cccc}0& 1& 0& 0\\ 1& 0& 1& 0\\ 0& 1& 0& 1\\ 0& 0& 1& 0\end{array}\right]$.

Solution proper

This restatement seems to be more complicated than the original expression. Indeed, this is not the type of solution one may expect for an olympiad-type question. However, the advantage here is that there exists a straightforward way to solve such a problem.

In general, for an arbitrary matrix, the maximum value of the expression above does not have a general formula (at least, to my knowledge). However, our matrix $M$ has a very crucial property: it is Hermitian. That is, it is its own conjugate transpose. To show this, since the matrix entries are all real, it suffices to show that the transpose of $M$ is itself.

This is important because it would mean that the quantity ${\displaystyle \frac{v^{T}Mv}{v^{T}v}}$ is precisely the Rayleigh quotient associated with the vector $v$ and Hermitian matrix $M$. An important property of the Rayleigh quotient is that its maximum value is the largest eigenvalue of the matrix.

Therefore, the alternative solution to our problem involves finding the eigenvalues of the matrix, which is a straightforward computation.

$$\begin{array}{rl}\det \left[\begin{array}{cccc}-\lambda & 1& 0& 0\\ 1& -\lambda & 1& 0\\ 0& 1& -\lambda & 1\\ 0& 0& 1& -\lambda \end{array}\right]& =-\lambda \det \left[\begin{array}{ccc}-\lambda & 1& 0\\ 1& -\lambda & 1\\ 0& 1& -\lambda \end{array}\right]-\det \left[\begin{array}{ccc}1& 0& 0\\ 1& -\lambda & 1\\ 0& 1& -\lambda \end{array}\right]\\ & =-\lambda (-\lambda ({\lambda }^2-1)-1(-\lambda ))-({\lambda }^2-1)\\ & ={\lambda }^2({\lambda }^2-2)-({\lambda }^2-1)\\ & ={\lambda }^4-3{\lambda }^2+1\end{array}$$

Using the quadratic formula, ${\lambda }^2={\displaystyle \frac{3\pm \sqrt{5}}{2}}={\left({\displaystyle \frac{1\pm \sqrt{5}}{2}}\right)}^2$. The eigenvalues of $M$ therefore are ${\displaystyle \frac{1-\sqrt{5}}{2}}$, ${\displaystyle \frac{\sqrt{5}-1}{2}}$, $-{\displaystyle \frac{1+\sqrt{5}}{2}}$, and ${\displaystyle \frac{1+\sqrt{5}}{2}}$. The largest among these is the latter.

Hence, the maximum value of ${\displaystyle \frac{1}{2}}{\displaystyle \frac{v^{T}Mv}{v^{T}v}}$ is ${\displaystyle \frac{1}{2}}\cdot {\displaystyle \frac{1+\sqrt{5}}{2}}=\boxed{{\displaystyle {\displaystyle \frac{1+\sqrt{5}}{4}}}}$, which agrees with our previous solution.

Some last comments

While this alternative solution gives a direct way to compute for the maximum value, it is still quite complicated to do and reliant on luck. For instance, the fact that a Hermitian matrix would appear was not really predicted. Additionally, finding the zeroes of the characteristic equation may also be difficult. Nevertheless, I still find this solution using linear algebra quite useful, and I hope you, the reader, also found this interesting.

As practice for the curious reader, I will leave the following problem for you to solve. I hope you will try out the method above in solving this problem. Thanks for reading!

Find the maximum value of

$$\begin{array}{r}\frac{y(x+z)}{x^2+y^2+z^2}\end{array}$$

where $(x,y,z)\in {\mathbb{R}}^3\setminus (0,0,0)$.