Playing with the Glome

Algebra Level 5

$2xy+4yz+6zw$

Let $M$ be the maximum of the expression above if $x^2+y^2+z^2+w^2=1$ , where $x,y,z$ and $w$ are real numbers. Write $M=\sqrt{p}+\sqrt{q}$ for two positive integers $p$ and $q$ , and enter $p+q$ .

Bonus question : For $axy+byz+czw$ , with the same constraint, express the maximum $M$ in terms of $a,b$ and $c$ .

The answer is 7.

2 solutions

Mark Hennings
Nov 15, 2015

The maximum of the quadratic form $2xy + 4yz + 6zw$ subject to the constraint $x^2 + y^2 + z^2 + w^2 = 1$ is, as usual, the maximum eigenvalue of the symmetric matrix defining the quadratic form. In this case the matrix is $A \; = \; \left( \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 1 & 0 & 2 & 0 \\ 0 & 2 & 0 & 3 \\ 0 & 0 & 3 & 0 \end{array} \right)$ The characteristic polynomial of this matrix is $\mathrm{det}(\lambda I - A) \; = \; \lambda^4 - 14\lambda^2 + 9 \; = \; (\lambda^2 - 7)^2 - 40$ and so the eigenvalues of the matrix are $\pm\sqrt{7 + \sqrt{40}} \,=\, \pm(\sqrt{5}+\sqrt{2}) \qquad \pm\sqrt{7 - \sqrt{40}} \,=\, \pm(\sqrt{5} - \sqrt{2})$ Thus $M \,=\, \sqrt{5}+\sqrt{2}$ , so the answer is $7$ .

In general, repeating these calculations for the matrix $B \; = \; \left( \begin{array}{cccc} 0 & a/2 & 0 & 0 \\ a/2 & 0 & b/2 & 0 \\ 0 & b/2 & 0 & c/2 \\ 0 & 0 & c/2 & 0 \end{array} \right)$ yields the characteristic polynomial $\lambda^4 - \tfrac{1}{4}(a^2+b^2+c^2) + \tfrac{1}{16}a^2c^2 \; = \; \left(\lambda^2 - \tfrac18(a^2+b^2+c^2)\right)^2 - \tfrac1{64}\big((a+c)^2+b^2\big)\big((a-c)^2+b^2\big)$ so that the largest eigenvalue is $\left(\tfrac18(a^2+b^2+c^2) + \tfrac{1}{8}\sqrt{\big((a+c)^2+b^2\big)\big((a-c)^2+b^2\big)}\right)^{\frac12}\;.$ After some algebra, this can be shown to to equal to $\tfrac14\left[\sqrt{(a+c)^2+b^2} + \sqrt{(a-c)^2+b^2}\right]\;.$

Yes, exactly! Very nice exposition! That's what I had in mind (+1).

Just a small detail to show that I have read your work: There are some square roots missing where you should have $\pm \sqrt{7\pm \sqrt{40}}$

Otto Bretscher - 5 years, 7 months ago

Thanks for spotting the typo. Correction made.

Mark Hennings - 5 years, 7 months ago

Oh you're back to Brilliant? My favorite user is back!!!! YIPEEE! Let's celebrate!

Pi Han Goh - 5 years, 6 months ago

So by your Spectral Theorem ,

$\dfrac{ \max(2xy + 4yz + 6zw) }{\min(2xy+4yz + 6zw)} = \frac{ \sqrt5 + \sqrt2}{-\sqrt5 - \sqrt2} = -1$

Right?

Pi Han Goh - 5 years, 6 months ago

Right!

The Spectral Theorem is a general result from Functional Analysis. In a very special case (finite-dimensional and real) it gives us the SED (symmetric eigenvalue decomposition) that Dr. Hennings explained so well: For any symmetric matrix $A$ there exists an orthogonal matrix $S$ such that $S^{-1}AS=S^TAS$ is diagonal.

The SED implies that the maximum and minimum of $q$ on unit vectors are the largest and smallest eigenvalues, respectively.

In this example, we could conclude that $\frac{\max(q)}{\min(q)}=-1$ without any computation, of course, just by switching two signs, $x$ and $z$ , say.

Otto Bretscher - 5 years, 6 months ago

@Otto Bretscher – .

The Spectral Theorem is a general result from Functional Analysis. In a very special case (finite-dimensional and real) it gives us the SED (symmetric eigenvalue decomposition)...

I'm already lost here. Haha. Anyway thanks for your reply! Comrade Otto

Pi Han Goh - 5 years, 6 months ago

@Pi Han Goh – Just start reading at "SED" then, Comrade... ;)

There is a complex version of this... just replace "symmetric" by "Hermitian" and "orthogonal" by "unitary"

Otto Bretscher - 5 years, 6 months ago

@Otto Bretscher – Is this problem solvable by quadratic forms?

Edit: Wait. Nevermind... there's a $xyz$ term.

Pi Han Goh - 5 years, 6 months ago

@Pi Han Goh – No, this is definitely not a quadratic form... not a single quadratic term! It looks like the kind of contrived problem that would have been created for the sole purpose of amusing the fans of classic inequalities.

Quadratic forms (as well as the closely related bilinear forms) are so important, among other things, because they are linked to the geometry of space: length, angles, distance, etc., that can be expressed in terms of inner products.

Otto Bretscher - 5 years, 6 months ago

To both Comrade Otto and Mr @Mark Hennings , I have some inquiries:

Question 1 : We must find convert the constraint to the sum of squares of variables = 1 first right? That is, if $x^2 + y^2 +z^2 + w^2 = 2$ , then we must first make the substitution of $x = \sqrt 2 X, y = \sqrt2 Y, z = \sqrt2 Z, w = \sqrt2 W$ . And if the answer is yes, why is it so? And does this method extends any number of variables (in this problem, there's 4 variables)?

Question 2 :
(a) So if I change the expression from $(2xy + 4yz + 6zw)$ to $(2xy + 2xz + 2xw + 2yz + 2yw + 2zw)$ , then the matrix is:

$A \; = \; \left( \begin{array}{cccc} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{array} \right)$

Right?

(b) With $\det(\lambda I - A) = 0$ , we get $\lambda$ is equal to the roots to the equation $x^4 - 6x^2 - 8x - 3 =(x-3)(x+1)^3= 0$ right?

Question 3 : Why must the matrix be symmetric? Is there a theoretical reason for it?

Question 4 : What does it mean if the characteristic polynomial have no real roots? Or is it impossible to occur? If it can occur, does it mean the expression has no max/min value? Is there any significance for non-real eigenvalues?

Question 5 : If the characteristic polynomial only has 1 distinct root? Does that mean that it is equal to the maximum and/or minimum value of the expression? Or is it impossible to occur?

Question 6 : How do you construct an expression like $2xy + 4yz + 6zw$ such that the eigenvalues are "nice" values like $\sqrt5 + \sqrt2$ ? This time, the matrix MUST be symmetric.

Pi Han Goh - 5 years, 6 months ago

Any quadratic form $q(x_1,x_2,\ldots,x_n) \; = \; \sum_{1 \le i,j \le n} a_{ij}x_ix_j$ can be written in the form $\mathbf{x}^T A \mathbf{x}$ where $\mathbf{x} = (x_1\;x_2\;\cdots x_n)^T$ and $A$ is a $n\times n$ real symmetric matrix. The matrix $A$ need not be symmetric, but it always can be, and there is a rich theory of symmetric matrices which we are using.

To be specific, for any real symmetric $n\times n$ matrix $A$ there is associated an orthonormal basis of eigenvectors. In particular, the characteristic polynomial of $A$ factorizes completely over the reals. This is equivalent to saying that there exists an orthogonal matrix $P$ such that $PAP^T$ is diagonal. Thus, if we change variables by setting $\mathbf{X} \; = \; P\mathbf{x}$ then the quadratic form becomes $\lambda_1X_1^2 +\lambda_2X_2^2 + \cdots + \lambda_n X_n^2$ where $\lambda_1,\lambda_2,\ldots,\lambda_n$ are the diagonal entries of $PAP^T$ . Since, moreover, $X_1^2 + X_2^2 + \cdots + X_n^2 \; =\; x_1^2 + x_2^2 + \cdots + x_n^2$ (because $P$ is orthogonal), maximizing/minimizing $q(\mathbf{x})$ over the unit hypersphere is just a matter of maximizing/minimizing $\lambda_1X_1^2 +\lambda_2X_2^2 + \cdots + \lambda_n X_n^2$ over the same unit hypersphere. It is easy to see that the result is just the largest/smallest eigenvalue of $A$ .

To answer one of your particular questions, if a symmetric matric has a single eigenvalue, then $PAP^T$ is a multiple of the identity matrix, and hence $A$ is a multiple of the identity matrix.

To find particular quadratic form with particular eigenvalues, start with the diagonal matrix that you want (pick the eigenvalues that you would like, say $\sqrt{5}+\sqrt{2}$ , $\sqrt{5}-\sqrt{2}$ and $3$ ), and play around with a choice of orthogonal matrix $P$ .

To learn the theory of all this, you need to check out books on Linear Algebra and on bilinear forms in particular.

Mark Hennings - 5 years, 6 months ago

Thank you for your detailed answer. Your explanation via hypersphere really nails it! Some follow up questions:

Question 7 :

The matrix $A$ need not be symmetric, but it always can be...

Can you give me an explicit example? Are you just performing some row operations? Or is there something more specific/in depth knowledge to it?

Question 8 :

To find particular quadratic form with particular eigenvalues, start with the diagonal matrix that you want (pick the eigenvalues that you would like, say $\sqrt{5}+\sqrt{2}$ , $\sqrt{5}-\sqrt{2}$ and $3$ ), and play around with a choice of orthogonal matrix $P$ .

Can you explain what "play around" means in this context?

Once again, thank you for being so patient in explaining all these to me. I learned some linear algebra in college via brainwashing, so I don't know what I'm actually learning. I think I only remembered what Gram Schmidt algorithm is for.

BIGGEST FAN!!!!

Pi Han Goh - 5 years, 6 months ago

@Pi Han Goh – to Question 7: The construction of the symmetric matrix $A$ of a quadratic form is straightforward: Make $a_{kk}$ the coefficient of $x_k^2$ and $a_{ij}=a_{ji}$ half the coefficient of $x_ix_j$ .

to Question 8 (we discussed this issue before): If you have a diagonal matrix $D$ and you want a symmetric matrix $A$ whose eigenvalues are the diagonal entries of $D$ , compute $A=S^{-1}DS=S^TDS$ for any orthogonal matrix $S$ .

Otto Bretscher - 5 years, 6 months ago

@Otto Bretscher – This sounds too easy to be true. Let me peruse it a few more times.

Pi Han Goh - 5 years, 6 months ago

@Pi Han Goh – Easy indeed... nobody said this stuff was hard.

Otto Bretscher - 5 years, 6 months ago

@Pi Han Goh – The result we are using is elegant and easy to apply, with implications that are very simply expressed. The theory, while involved, is also very elegant. The ability to diagonalize matrices, as we do here, is an important weapon in the Linear Analyst's arsenal. That symmetric matrices are diagonalizable has many applications; the existence of principal modes of oscillation about a point of stable equilibrium in mechanics problems, and the existence of energy levels in quantum mechanics are (basically) two of them!

Mark Hennings - 5 years, 6 months ago

@Mark Hennings – Wow! You really do know everything! Thanks for the conversation!

Pi Han Goh - 5 years, 6 months ago

Wow, I see that while I was sleeping you guys had a wonderful discussion on quadratic forms. Thank you so much for this lucid explanation, Dr. Hennings.

Otto Bretscher - 5 years, 6 months ago

汶良林
Nov 27, 2015

Can you show us that the maximum is attained?

Otto Bretscher - 5 years, 6 months ago

汶良林 - 5 years, 6 months ago

Yes, that will work, but the solution involves some pretty tedious computations (finding $a,b,c,d,e,f$ ). This seems like an interesting alternative, but Dr. Hennings' solution is more direct and general. Mathematically, solving your six equations is equivalent to finding the roots of the characteristic polynomial.

Otto Bretscher - 5 years, 6 months ago

@Otto Bretscher – Yes! Dr. Hennings' solution is more direct and general. But how to get the value of x, y, z, w when the maximum occur?

汶良林 - 5 years, 6 months ago

@汶良林 – The maximum of the quadratic form is attained at the two unit eigenvectors associated with the maximum eigenvalue $\lambda=\sqrt{2}+\sqrt{5}$ . To find these eigenvectors, solve the linear system $A\vec{v}=\lambda \vec{v}$ , a quick and routine task. One eigenvector is $\vec{v}=(6, 6\lambda, 3\lambda^2-3, \lambda^3-5\lambda)$ ... now normalize.

Otto Bretscher - 5 years, 6 months ago

@Otto Bretscher – Thank you very much!

汶良林 - 5 years, 6 months ago

@汶良林 – I thank you for your solution! It is good to see that, with great effort, this problem can be solved with algebra alone (in the old sense of "algebra": solving equations)

Otto Bretscher - 5 years, 6 months ago

Playing with the Glome

The answer is 7.

2 solutions

0 pending reports