Wikipedia:Reference desk archive/Mathematics/2006 September 15

From Wikipedia, the free encyclopedia

< September 14 Mathematics desk archive September 16 >
Humanities Science Mathematics Computing/IT Language Miscellaneous 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 at one of the pages linked to above.
< August September October >


Contents

[edit] September 15

[edit] Quadratic forms

What is the typical way of working with quadratic forms with added linear terms? Diagonalization of the associated matrix, and then folding in the linear terms through translation?

I have not spent too much time thinking about this yet, but I wonder whether it would be more elegant to consider x^T = (1 x y), and defining a 3 by 3 matrix M so that x^T M x = 0 is what we want to work with. Is this what is typically done for such things?--HappyCamper 00:33, 15 September 2006 (UTC)

Depends what you're doing. Examples:
  • projective (homogeneous coordinates): \begin{pmatrix} x & y & 1 \end{pmatrix} \ \begin{pmatrix} a & b & c \\ d & e & f \\ g & h & i \end{pmatrix} \ \begin{pmatrix} x \\ y \\ 1\end{pmatrix} , where the matrix is usually restricted to be symmetric or triangular
  • polynomial: \begin{pmatrix} x & y\end{pmatrix} \ \begin{pmatrix} a & b \\ d & e \end{pmatrix} \ \begin{pmatrix} x \\ y\end{pmatrix} + \begin{pmatrix} j \\ k\end{pmatrix} \ (x \ \ y) + m , where the matrix is almost always symmetric.
  • eliminate the linear terms -- the method is usually taught in analytic geometry as the method of moving conic sections into standard form -- i.e. rotate to eliminate cross terms, complete squares, and represent the result as, for example, \frac{(x-h)^2}{a^2}+\frac{(x-k)^2}{b^2} \ = \ 0 .
From the point of view of the theory of quadratic forms inclusion of linear or constant terms is an affine transformation, suggesting that the first or third is more natural when extending from that theory. However, it is equivalent to the polynomial form and sometimes the polynomial form is more convenient for expressing certain proofs. Despite this, both of the displayed forms above are inconvenient for cubes and higher, so the Einstein notation is commonly used. This notation is fundamentally equivalent to the polymer form above, but is both more compact and easier to work with (with some practice, because initially you don't realize just how many relations you've written down with one equation). -- Fuzzyeric 02:28, 15 September 2006 (UTC)
By definition, a quadratic form has no linear terms. But suppose we have a quadratic polynomial in two variables, such as one used for the implicit equation of a rotated and displaced ellipse,
0 = 481x^2-216xy+544y^2-1920x-1440y-6400 . \,\!
Using homogeneous coordinates we can rewrite this so all terms have total degree 2.
0 = 481x^2-216xy+544y^2-1920xw-1440yw-6400w^2 . \,\!
Et voila! We have a polynomial of degree 2 which is homogeneous in the sense that all terms have the same degree, and thus a valid candidate for a quadratic form in three variables. As with any quadratic form, we can convert this to a bilinear form, and hence to a symmetric matrix, your proposed M.
0 \,\! {} = \bold{x}^T M \bold{x} \,\!
{} =  \begin{bmatrix}w&x&y\end{bmatrix} \begin{bmatrix} 6400&-960&-720\\ -960&481&-108\\ -720&-108&544 \end{bmatrix} \begin{bmatrix}w\\x\\y\end{bmatrix}
Indeed, this is a convenient and popular technique in applications like computer graphics. The matrix has uses that are not immediately obvious. For example, suppose p is a point outside the ellipse; then
0 = \bold{p}^T M \bold{x} \,\!
is the equation of a line intersecting the ellipse in the two points where a ray from p is tangent. (This line is called the "polar" of "pole" p.) If p is on the ellipse, then this line goes through p and is tangent to the ellipse there. Or consider the last column of M; it gives the homogeneous coordinates for the center of the ellipse.
So congratulations, your instincts in this are quite fruitful. --KSmrqT 05:29, 15 September 2006 (UTC)
Thanks for the elaborate responses - this is quite helpful. I think I am most interested in the homogeneous coordinate representation. What I am unsure of, is the interpretation of this result...
From above, we have \bold{x}^T M \bold{x} = 0 \,\!. Now, since M is symmetric, there exists an orthogonal matrix O such that \bold{x}^T \bold{O}^T \bold{D} \bold{O} \bold{x} = 0 \,\!. D is a diagonal matrix which will tell us everything about the conical intersection centered at the origin. Now, what does the product \bold O \bold{x} mean? This seems to be an affine transformation on the original coordinate system. However, is it not true that we are transforming the identity element as well when this is done? This is what seems odd. --HappyCamper 16:05, 15 September 2006 (UTC)
From Morse theory every quadratic equation is equivilent to Ax2+By2 when translation and rotation are removed. The equation will generally have one critical point, \bold{p} say. What happens with the transformation is that \bold O \bold{p} = 0, \bold{D} \bold{O} \bold{p}=0 and \bold{O}^T \bold{D} \bold{O} \bold{p}=\bold{p}, that is it leaves the critical point stationary.--Salix alba (talk) 19:10, 15 September 2006 (UTC)
Equivalently, the matrix O rotates the coordinate unit vectors to be parallel to the eigenvectors of the matrix. Equivalently, rotates the matrix to be diagonal (each ellipsoid axis is parallel to a coordinate axis). -- Fuzzyeric 04:05, 16 September 2006 (UTC)
The term "identity element" is misplaced. If (w:x:y) are the homogeneous coordinates of a point, each point in the plane is defined by an infinite number of triples, all non-zero scalar multiples, (σwxy), σ ≠ 0. That's the reason we often use colons (":") rather than commas (","); only the ratios matter. We are definitely not obliged to have w = 1. In fact, we have a whole line of points with w = 0, sometimes called "points at infinity".
Although we can diagonalize M with an orthogonal matrix Q, we can also use any invertible matrix A. For example, let
A = R T S = \begin{bmatrix}4/5&-3/5&0\\3/5&4/5&0\\0&0&1\end{bmatrix} \begin{bmatrix}1&0&3\\0&1&0\\0&0&1\end{bmatrix} \begin{bmatrix}5&0&0\\0&4&0\\0&0&1\end{bmatrix} .
This will diagonalize σM, where σ = 10−4 and M is the matrix that I used as my example, producing a circle x2+y2w2. (Note that the scalar σ has no effect in homogeneous coordinates.) We see that A is merely an affine change of coordinates, combining rotation, translation, and non-uniform scaling. The matrix has been reduced to a diagonal form involving only +1, −1, and 0, revealing the signature of the quadratic. Acting on points p, the effect of A is to transform them into a coordinate system where points on the ellipse become points on an origin-centered unit circle. --KSmrqT 05:37, 17 September 2006 (UTC)
This description is quite useful. The note about Morse theory is quite intriguing too. So it seems, a better way to think of this, is that in homogeneous coordinates, the introduction of w induces a convenient parameterization of the problem. I must read up on this more. This is far, far, far too interesting to be missing out on. --HappyCamper 03:05, 18 September 2006 (UTC)

[edit] The red car or the blue car?

The terrorists has stolen a nuclear device and escaped with the help of a truck. Chasing after them in his Lotus is James and his two gadgeteers Q and R.

Catching up to the truck in a back alley way, James watched helplessly as the terrorists abandoned the truck for two getaway cars. The red car sped away to the east while the blue car sped away to the west.

Luckily Q and R aim their prototype radiation detector (disguised as CANON and NIKON digital SLR cameras respectively) at the two separate cars as they disappeared in the distance. Q aimed at the red car while R aimed at the blue car.

Since there is only one nuclear device, it's not certain which car contains the nuke.

Q said "My detector has detected the nuke in the red car. If the red car do indeed have the nuke, my detector will say so in 85% of the time!"

R injected "But if the red car do not have the nuke, Q's detector will give a false positive 70% of the time!"

R said "My superior detector did not detected any nuke in the blue car. If the blue car does not have the nuke, my detector will give a negative (or true reading) 98% of the time. On the otherhand if the blue car do have the nuke, my detector will also give a false negative 60% of the time."

Question: Which car should James go after?

210.49.155.134 10:04, 15 September 2006 (UTC)

Here's the chances each result would be found under each scenario:
Scenario 1     Q results   R results
==========     ==========  ==========
Red has nuke   85% chance
Blue doesn't               98% chance

Scenario 2 
========== 
Blue has nuke              60% chance
Red doesn't    70% chance
I would multiply the results, to get a (0.85)(0.98) or 83.3% chance we would get both the Q and R results if Scenario 1 is correct, and a (0.60)(0.70) or 42% chance if Scenario 2 is correct. Let's normalize those results to get 83.3/(83.3+42) or around a 66.5% chance the red car has the nuke and 42/(83.3+42) or around a 33.5% chance the blue car has the nuke. StuRat 10:25, 15 September 2006 (UTC)
Recommend using Bayesian analysis to estimate the posterior probability that the bomb is in each car given the data. This explains the method used by StuRat. -- Fuzzyeric 04:12, 16 September 2006 (UTC)
Since the problem involves the event 'positive Q' and 'negative R readings', we need to know whether Q and R detectors are independent in order to solve the problem. (Igny 16:13, 17 September 2006 (UTC))

I things it is implied that the detectors are independent. M.manary 17:20, 17 September 2006 (UTC)