Wikipedia:Reference desk/Archives/Mathematics/2006 November 25

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

November 25

Transformations and Eigenvectors

After recently reading the article on eigenvectors, I have become a little confused. We studied eigenvectors with matrices (as is often the case according to the article).

All matrices are linear transformations, and because of that they have eigenvectors and eigenvalues. That is fine if te matrix is square. A transformation of R³ to R³ obviously could have eigenvectors, but what about non-square matrices, lets say 3 x 2. This matrix obviously still defines a linear transformation but cannot possibly have eigenvectors because the vectors in the two different spaces R³ and R² cannot be compared. Am I correct or am I missing something?

Also the article on eigenvectors claims that transformations have eigenvectors. Is this generalisation true, it is obviously true for linear transformations but what about non-linear transformations, like f(x,y)=(x²,y)? Do they or can they also have eigenvectors and eigenvalues? Or will these just always be empty sets? --payxystaxna 11:25, 25 November 2006 (UTC)

Footnote (1) to the article states: "In this context, only linear transformations from a vector space to itself are considered." In terms of a matrix, this means it is square. Apparently it is not a good idea to use the same format for footnotes that must be read for comprehension as for references to citations that can safely be skipped.  --Lambiam^Talk 16:33, 25 November 2006 (UTC)

As for your second question, it is of course possible for a non-linear transformation to have eigenvectors (in your example, (1, 1) is an eigenvector of 1); but, as opposed to linear transofrmations, their existence is not guaranteed, and they need not form a vector space. -- Meni Rosenfeld (talk) 20:51, 25 November 2006 (UTC)

Thanks guys, the second question explains why the footnote is where it is (I somehow missed it completely).-- payxystaxna 12:57, 26 November 2006 (UTC)

Is the existance of eigenvectors to a linear transformation guaranteed?! How about the matrix

${\begin{pmatrix}0&-1\\1&0\end{pmatrix}},$

which rotates a vector in $\mathbb {R} ^{2}$ by the angle $\pi /2$? —Bromskloss 17:23, 26 November 2006 (UTC)

Well, I was of course making the assumption that we are working over an algebraically closed field. So that matrix has eigenvalues ±i when viewed over $\mathbb {C}$. Sorry for not clarifying myself. -- Meni Rosenfeld (talk) 17:57, 26 November 2006 (UTC)

On the other hand, a shear parallel to the x axis, matrix

${\begin{bmatrix}1&1\\0&1\end{bmatrix}},$

has only one eigenvalue (and one eigenvector), not two. This is true even for complex vectors. --KSmrq^T 04:16, 27 November 2006 (UTC)

I blew the dust off my first year linear algebra textbook, and found this interesting example, showing that not all linear transformations have non-zero eigenvectors.

The rotation of the real plane anti-clockwise through the angle θ (0 < θ < π) is obviously a linear transformation. This transformation has no eigenvectors. So the existence of eigenvectors of linear transformations is non guaranteed.

This makes my original question all the more erroneous, I sincerely apologise. I should have just pulled the textbook off the bookkase in the first place. I do think that the article needs a little revision to eliminate confusion. I will be discussing it on the talk page for that article.

Apologies again --payxystaxna 20:57, 27 November 2006 (UTC)

If you read our replies again, you will see that Bromskloss has already given the example of a rotation, and that I have therefore clarified that the guarantee is for algebraically closed fields (such as the field of complex numbers). As KSmrq has pointed out, this assumptions doesn't guarantee the stronger demand to have as many linearly independent eigenvectors as the algebraic multiplicity of the eigenvalue. -- Meni Rosenfeld (talk) 21:07, 28 November 2006 (UTC)

two optimization problems

i am working on two problems that deal with optimization/maximums/minimums for school. ive only been able to partially solve them because i dont know what to do next. can anyone give me some guidance of what to do next?

(1) a retangle is inscribed in a triangle /_\ so that the rectangle touches the bottom & both sides of the triangle. what is the ratio between the triangles area & the rectangles area when the rectangles area is maximum?

my reasoning: the rectangles area is maximum when it is a square, in other words when both the length & the width are equal. also i know that the smaller triangle formed by the top of the rectangle intersecting the bigger triangles 2 sides is similar to the big triangle because the top of the rectangle is parallel to the bottom of the big triangle. but i am not sure how to unite these 2 facts.

ok I'm assuming the triangle is isosceles but the top angle can be anything between 0 and 180 degrees. You need to find a formulas relating the height and bottom length of the triangle to the height and length or the rectangle. Clue: get the area of the rectangle as a function of either the bottom length of the rectangle or the height of the rectangle. Then find the maximum value for that equation - (it's a quadratic equation).

So you'll need B length of base of triangle, H height of triangle, L length of rectangle and W width of rectangle. Hope that helps (it's not necessarily a square..) 83.100.138.7 00:02, 26 November 2006 (UTC)

(2) prove that the output (y value) of the function f(x) = 1/(2x^2 - x + 1) ≥ 8/7 always.

my reasoning: i graphed the function on my calculator & sure enough that is the maximum output, but i cant derive that fact. i tried approaching it as a quadratic equation, perhaps thats the problem its really a rational equation. (what i did was try to find the axis of symmetry of the bottom of the function = -b/2a = 1/2 but plugging that in for x doesnt give the maximum y value) if it is a rational equatrion i dont know how to "prove" the maximum except by graphing.

any help would be much appreciated. thanks, r —The preceding unsigned comment was added by 162.83.146.34 (talk • contribs) 23:27, November 25, 2006 (UTC).

Find the minimum of the function (2x^2 - x + 1) - I guess you can do this.. (if not plot it out - it's a parabola - you should have a method for finding the bottom of the parabola

Then if that is the the minimum then 1/(2x^2 - x + 1)will be the maximum value.

But I've checked your problem and it looks like there's a mistake - as written f(x) is less than or equal to 8/7 not greater than? 83.100.138.7 00:02, 26 November 2006 (UTC)

eg if x=4 1/(2x^2 - x + 1) = 1/(2*4*4 - 4 +1)= 1/ (32-4+1) = 1/29 which is less than 8/7. My guess is it's supposed to be the other way round.

You were right to try to find the axis of symmetry for the quadratic (it's at x=1/4 try again), get this axis value right and I think you will have solved it. Good luck. 83.100.138.7 00:10, 26 November 2006 (UTC)

Both problems may be solved using calculus; specifically using the first derivative of the expression for area or f(x) to argue about the maximums and/or minimums of these functions. I suspect your first solution about the triangle is incorrect, but I'd have to think about it for a little bit before I could give you a definite answer on that. - Rainwarrior 23:35, 25 November 2006 (UTC)

Or alternatively, if both equations are quadratic you can find the max/min by completing the square. - Rainwarrior 00:49, 26 November 2006 (UTC)

Doesn't completing the square solve the equation, but not find the maxima/minima? 83.100.138.7 00:59, 26 November 2006 (UTC)

By expressing a quadratic polynomial y in the form y = a(x−u)²+b, assuming that a ≥ 0 we see now easily that b is a lower bound, because y ≥ b for all values of x. Furthermore, we see that it is a sharp lower bound; in other words, the minimum is equal to b, since it is attained for x = u.  --Lambiam^Talk 06:30, 26 November 2006 (UTC)

Oh yes, silly me.87.102.12.129 15:23, 26 November 2006 (UTC)

Well, completing the square turns your quadratic polynomial into the standard formula for a parabola. The minimum/maximum of a parabola is found at the point where the squared term is equal to zero. If the squared term is $(ax+b)^{2}$ then solve $ax+b=0$ for x, which will tell you exactly for what value of x the function is maximized or minimized. (After this, simply substitute this value for x into the formula to find the value of the function at its max/min.) - Rainwarrior 06:38, 26 November 2006 (UTC)

As to the first problem: take some triangle (assumed to have a horizontal bottom side) with a proper rectangle, where proper means that its bottom rests on the bottom of the triangle while touching both other sides. Let the ratio of the area of the triangle to that of the square be R. If we change the scale of the configuration, R does not change; it is scale-insensitive. Now change only the vertical scale; say by stretching everything vertically. The stretched rectangle will still be proper with respect to the stretched triangle, and the ratio is still R. So if R was at its maximum before, it is still at its maximum; and conversely, it it is now at its maximum, it was so before. Being square is not invariant under stretching and therefore cannot be a property of optimal proper rectangles in general.

Now instead of this stretching exercises we do another transformation. Think of the rectangle as firmly holding on to the sides of the triangle where it touches, giving a rigid line segment between these points, with the rest of the rectangle hanging down from there. Now push the top of the triangle horizontally to one side. The bottom side is fixed. This does not change the area of the triangle (height × bottom / 2). The rectangle shifts sidewise with the triangle, its bottom sliding over the triangle's bottom side. Its shape, and therefore its area, does not change. So R does not change. We conclude that the size of the optimal rectangle does not depend on the angles of the triangle, but only on the lengths of its bottom and height.

By a combination of re-scaling and horizontal skewing we can transform any triangle shape into any other. So if we solve the problem for any triangle we have solved it for all triangles. So take an isosceles right triangle, where the right angle is, say, at the left bottom corner. Each proper rectangle shares that corner. For reasons of symmetry, it is immediate that the case of a square is extremal (minimal or maximal). By expressing the area as a function of the length of the rectangle's bottom side you can easily find the optimum (by completing the square, as mentioned before).

Of course, you can also directly solve the general case; then the easiest is to take the height of the rectangle as the variable. But by the reasoning I sketched above, you can actually solve the problem fully in your head, without using pencil and paper (or chalk and blackboard, or keyboard and screen).  --Lambiam^Talk 07:15, 26 November 2006 (UTC)

(edit conflict)

Maybe now is a good time to review from the beginning.

We are given a triangle with base 2b and height h, assumed isosceles.

If we split it down the middle with a perpendicular, we get two half-rectangles (cut on the diagonal) with width b and height h; thus the area of the triangle is bh.

Inscribe a rectangle whose base is a fraction, α, of the triangle base. Thus when α is zero the rectangle has base zero and height h, and when α is one the rectangle has base 2b and height zero. For α between these two extremes, the height varies linearly; it is (1−α)h. Likewise, the base varies linearly; it is 2αb. Therefore the area of the rectangle is 2α(1−α)bh.

When we take the ratio of the areas, we discover that the dimensions of the triangle make no difference. However, the ratio does depend on α; it is 2α(1−α). This is what we must maximize.

If we shear the triangle to one side, its area does not change. Assume the shearing does not go beyond creating a right triangle. Then the top corners of the rectangle slide over with the shear, and the bottom corners can stay directly beneath them. Thus we can still fit the same rectangle. Challenge: Can we fit a larger rectangle? (Try finding the largest rectangle in a right triangle.) --KSmrq^T 07:53, 26 November 2006 (UTC)

Correction: the base is αb, the area α(1−α)bh.87.102.12.129 14:37, 26 November 2006 (UTC)

Correction²: A fraction α of triangle base 2b is 2αb.  --Lambiam^Talk 15:35, 26 November 2006 (UTC)

Removes correction soryy 87.102.12.129 15:42, 26 November 2006 (UTC)

Finishing off: Area=A=a(1−a)bh = bh(a-aa) dA/da = bh(1-2a) maximum at the top of parabola ie when dA/da=0 ie 1-2a=0 a=0.5 Therefore A=0.5(1-0.5)bh=0.25bh The area of the triangle=2bh/2=bh

So the ratio of area of triangle to rectangle (at maximum erctangle area) is 4:1 when both the base and height of the rectangle are half the lengths of the base and heights respectively of the triangle.87.102.12.129 14:36, 26 November 2006 (UTC)

Except that the correct answer is 2:1.  --Lambiam^Talk 15:35, 26 November 2006 (UTC)

Yes. 87.102.12.129 15:42, 26 November 2006 (UTC)

original poster: thanks so much for your help. you guys are the greatest. but i still have not understood how to get all the way to the end. heres where i am now:

1) i was following the proof leadingn up to the ratio 2:1 until one poster introduced dA/da, a notation im not familiar with. 2) someone said i was right to try to find the axis of symmetry. am i solving for it wrong though? 1/(2x^2 − x + 1) ; isolate the polynomial in the denominator, 2x^2 − x + 1 ; axsym = −b/2a = −(−1)/2(a) = 1/2 ; substitute into the equation: 1/(2(1/2)^2 − (1/2) + 1) = 1/(2(1/4) − (1/2) + 1) = 1/((1/2) − (1/2) + 1) = 1/1 = 1 anyone who can clear up my lingering doubts, i will be indebted to them forever :-)

(1) dA/da means the derivative of the (dependent) quantity A with respect to variable a (which before was called α). If you don't know differential calculus, then just ignore this, and instead find the value of α that maximizes α(1−α) by any other method. The ratio area-of-triangle : area-of-square is then 1 : 2α(1−α).

(2) When you write "axsym = −b/2a = −(−1)/2(a)", what is the value of a? It is not 1, so −(−1)/2(a) = 1/2 is incorrect.  --Lambiam^Talk 19:33, 26 November 2006 (UTC)

You're trying to find the axis of symmetry for 2x^2 − x + 1 . Your equation is of the type ax^2+bx+c which can be written a(x^2+bx/a+c/a) = a((x+b/2a)²-b²/4a²+c/a); There fore it is symmetry about x=-b/2a where b=-1 a=2 So axsym = −b/2a = −(−1)/2x2 = 1/4 . a=2 not 1 - you just missed that. That should explain it..83.100.250.53 20:38, 26 November 2006 (UTC)

Ahem, in helping people with their homework we try not to give away the whole solution and do it all the way for them, but just to help them over the spot where they got stuck.  --Lambiam^Talk 23:43, 26 November 2006 (UTC)

Based on our calculations so far, it will be more convenient to work with the area ratio of rectangle to triangle, which I have summarized above.

${\begin{aligned}R:T&{}=2\alpha (1-\alpha )bh:bh\\&{}=2\alpha (1-\alpha ):1\end{aligned}}$

Please, what kind of school course attempts to teach optimization without calculus? It is the standard tool!

Although I did provide some geometric insight to simplify the problem, Lambiam is quite right that providing a full solution is inappropriate, so I did not and will not do that. What I will do is discuss how to find the maximum of a polynomial.

As in the actual problem, we will assume that x must be between 0 and 1.

Begin with the simplest case, a constant polynomial, p(x) = c. No matter what value we choose for x, p has the value c, so that is the maximum.

Next consider a linear polynomial, p(x) = bx+c. We assume b is nonzero, else we have only a constant. If b is positive, then p increases as x increases; the maximum is at the maximum x, namely at 1. If b is negative, then p decreases as x increases; the maximum is at the minimum x, namely at 0.

Finally we consider a general non-linear polynomial,

$p(x)=c_{n}x^{n}+c_{n-1}x^{n-1}+\cdots +c_{1}x+c_{0}.\,\!$

We are assuming that n is greater than 1 and that c_n is nonzero. Now the possible locations for a maximum are richer. For example, consider

$q(x)=256x^{9}-576x^{7}+432x^{5}-120x^{3}+9x.\,\!$

It attains its maximum value, which is exactly 1, at three places within our allowed range. One place is at the upper boundary, x = 1. The other two places are in the interior, at x values of approximately 0.174 and 0.766 (roots of 8x³−6x+1).

We can easily test the boundaries, but how do we find any maximum in the interior? The answer is to examine the polynomial behavior at each point in microscopic detail. We will see only two possibilities: either it looks flat like a constant polynomial, or it looks tilted like a linear polynomial. Within the interior we are free to vary x up or down, so a closeup with a tilted appearance cannot be at a maximum. Therefore we want to find values of x for which a tiny change in x makes no difference in p.

Formally, our "microscope" is differential calculus. Our reasoning tells us we must solve

$p'(x)=0,\,\!$

where p′ is the derivative of p with respect to x.

We will explore this in a moment; however, this is not quite enough. Consider the point x = ¹⁄₂ in our example; although the derivative is zero there, this happens to be a minimum (q(¹⁄₂) equals −1), not a maximum. For our present purposes it will suffice to compute the value of q at such points, choosing only the largest. Still, this narrows our possibilities considerably.

Now to see how our microscope works, consider a polynomial with only one term,

$f(x)=ax^{4}.\,\!$

If we change x by a tiny amount, which we will call ε per tradition, the result is

${\begin{aligned}f(x+\varepsilon )&{}=a(x+\varepsilon )^{4}\\&{}=a(x^{4}+4x^{3}\varepsilon +6x^{2}\varepsilon ^{2}+4x\varepsilon ^{3}+\varepsilon ^{4})\\&{}=ax^{4}+4ax^{3}\varepsilon +6ax^{2}\varepsilon ^{2}+4ax\varepsilon ^{3}+a\varepsilon ^{4}.\end{aligned}}$

We find variation by subtracting the f on which our microscope is centered,

$f(x+\varepsilon )-f(x)=4ax^{3}\varepsilon +6ax^{2}\varepsilon ^{2}+4ax\varepsilon ^{3}+a\varepsilon ^{4},\,\!$

and look for the nature of the variation by dividing by the input change, ε.

${\frac {f(x+\varepsilon )-f(x)}{\varepsilon }}=4ax^{3}+6ax^{2}\varepsilon +4ax\varepsilon ^{2}+a\varepsilon ^{3},\,\!$

Discarding the terms in which ε remains, we retrieve the object of interest, the derivative of f with respect to x.

$f'(x)=4ax^{3}\,\!$

When we apply the same procedure to our general polynomial, the result is

$p'(x)=nc_{n}x^{n-1}+(n-1)c_{n-1}x^{n-2}+\cdots +c_{1}.\,\!$

Thus in the case of our example we find

$q'(x)=2304x^{8}-4032x^{6}+2160x^{4}-360x^{2}+9.\,\!$

Luckily, this factors as

$q'(x)=9(2x-1)(2x+1)(8x^{3}-6x-1)(8x^{3}-6x+1),\,\!$

so we can find all the zeros in closed form. In particular, we can see that both ¹⁄₂ and the roots of 8x³−6x+1 will give zeros. We note that −¹⁄₂ also produces a zero, but it is outside our boundaries so we discard it.

The rectangle-in-triangle problem is much simpler, and should now be manageable. --KSmrq^T 06:54, 27 November 2006 (UTC)

To 83.100.138.7 and KSmrq (and possibly other posters — sorry, if I missed someone): the assumption of the triangle being isosceles is superfluous.
Let's mark triangle vertices A, B and C, and the altitude from C – H. We also mark the rectangle vertices, say M, N, P, Q, so that M and N belong to AB, and M is between A and N, P belongs to BC, Q belongs to AC. And of course name the rectangle's height: h = QM = PN.
Now we shift the AMQ triangle by vector MN to join it with NBP and get a new triangle A'BP. It's obvious we got two triangles, A'BP and QPC, both similar to ABC. The similarity gives simple proportions of corresponding distances:

any length in A'BP = h/H × corresponding length in ABC

any length in QPC = (H-h)/H × corresponding length in ABC

That leads to:

Area(A'BP) = h²/H² × Area(ABC)

Area(QPC) = (H-h)²/H² × Area(ABC)

Finally area of the rectangle:

Area(MNPQ) = Area(ABC) - [ Area(AMQ) + Area(NBP) + Area(QPC) ]

= Area(ABC) - [ Area(A'BP) + Area(QPC) ]

= Area(ABC) × [ 1 - h²/H - (H-h)²/H² ]

= Area(ABC) × [ H² - h² - (H-h)² ]/H

= Area(ABC) × 2[ Hh - h² ]/H²

= some constant × ( Hh - h² )

It can be shown by elementary means that such quadratic function has one maximum, and where it is.
Please note the whole solution does not need an assumption that ABC is isoscels. There's even more: we actualy don't need MNPQ being rectangle! The same solution (and same answer) applies to any quadrilateral parallelogram, as long as its angles are bigger than those of ABC (otherwise we would be unable to place P and Q on AC and BC, while M and N between A and B.)
Regards, CiaPan 16:42, 28 November 2006 (UTC)

Lambiam and I both varied the shape of the triangle. Did you miss that? Although I began with an isosceles triangle for simplicity, I then skewed it as far as a right triangle. This being homework, I purposely did not complete the analysis. Similarly, Lambiam covered much the same ground, but in reverse. Arguments were given that scale did not matter, nor skew; then a right triangle was analyzed. You have now addressed the same point in yet another way!

So let's take advantage of the opportunity to teach. One lesson here is that there is no single right way to approach a problem. Different mathematicians bring different strengths, preferences, and training. Sometimes altering our view of a problem is exactly what we need to find a solution, so we wish to cultivate flexibility. Too many students are imprinted with the pattern of a typical textbook: one problem, one solution. Outside the class, that leads to failure. --KSmrq^T 22:29, 28 November 2006 (UTC)

To original poster: your second problem is in fact very easy. Forget calculus! You certainly don't need it here. You don't need a parabola graph and its symmetry axis, either.
Just look again at the polynomial in the denominator:

D = 2x² - x + 1.

You certainly can complete the square, converting D(x) to the form:

D = const1×((x + const2)² + const3)

It's pretty obvious that for real values of x the minimum value of (x+const2)² is zero. If const1 and const3 are both positive, that implies the minimum value of D(x) is const1×const3, which in turn means 1/D is always greater or equal const3/const1.
You just need to calulate the two 'const' values to prove the statement opposite to that in your problem:

1/D(x) ≤ 8/7 always.

--CiaPan 19:17, 28 November 2006 (UTC)

Again, this is homework. We deliberately do not completely solve the given problem. My optimization-as-calculus presentation was, in part, designed to respect that. It was also intended to give all interested readers a framework in which to place optimization of any differentiable function with boundary constraints. I did not explicitly state the Karush-Kuhn-Tucker conditions, nor raise the distinction between a global maximum and a local maximum, but did hint at the need for such considerations. Real-world application of optimization can be more complicated still; see, for example,

• Gill, Philip (1981). Practical Optimization. Academic Press. ISBN 978-0-12-283952-8. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

For human interest and perhaps inspiration, here is some background about one of its authors, Margaret Wright. --KSmrq^T 22:29, 28 November 2006 (UTC)