Wikipedia:Reference desk/Archives/Mathematics/2011 December 4

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.

December 4

Question about eigenvectors and eigenvalues

Hi Reference Desk, I have 2 questions about eigenvectors and eigenvalues in the context on Singular Value Decomposition.

In my linear algebra textbook (undergraduate), it says that |Ax| = |λx| = |λ| |x| = |λ|. I understand how it goes from |Ax| to |λ| |x|, but I don't understand how it went from |λ| |x| to just |λ|.

Also, in an example where a matrix A is described to linearly transform a unit sphere {x: |x| = 1} in R^3 onto an ellipse in R^2, we were told to find a unit vector at which the length |Ax| is maximized and compute this maximum length. The solution says that the quantity |Ax|^2 is maximized at the same x that maximizes |Ax| (which I understand), but it also says that |Ax|^2 = (Ax)^T(Ax) = x^T A^T A x = x^T (A^T A) x. Why is it that |Ax|^2 = (Ax)^T (Ax) ?

Thanks — Preceding unsigned comment added by 169.232.119.135 (talk) 06:57, 4 December 2011 (UTC)

For the first one, presumably x is a unit vector. I think the context is needed.

For the second one, it's a well known identity that $|x|^{2}=x^{T}x$ for any vector x. $|x|$ is by definition ${\sqrt {x\cdot x}}$ and it should be pretty obvious that $x\cdot x=x^{T}x$. If you choose some arbitrary x and you try to calculate $x\cdot x$ and $x^{T}x$ you will find that you really use literally the same procedure for evaluating both of them. Widener (talk) 07:08, 4 December 2011 (UTC)

Thanks Widner, I now understand those 2 problems. The context for the first question was indeed where x is a unit vector. — Preceding unsigned comment added by 169.232.72.232 (talk) 19:07, 4 December 2011 (UTC)

Algebra Problem

Find all pairs of real numbers (x,y) such that 16^x2+y+ 16^x+y2=1 117.227.104.36 (talk) 14:07, 4 December 2011 (UTC)

Is this homework? If so, we can only give hints. Turn the LHS into a function, find its absolute minima, etc. It comes out neatly (I think). We'll help more if you convince us it isn't homework, and ask nicely, etc. IBE (talk) 15:49, 4 December 2011 (UTC)

Hint, the answer(s) are in neat format. And note that any values of x and y where either is 1 or larger in absolute value will give a value that is too large.Naraht (talk) 16:16, 4 December 2011 (UTC)

$\left(-{\frac {1}{2}},-{\frac {1}{2}}\right)$ Widener (talk) 01:08, 5 December 2011 (UTC)

Closed form series solution

Please help me evaluate

• $\sum _{n=0}^{\infty }{\frac {1}{(n+{\tfrac {1}{2}})(n-{\tfrac {1}{2}})}}x^{n}=-{\frac {1}{4}}{}_{2}F_{1}(-{\tfrac {1}{2}},0;{\tfrac {3}{2}};x)$

in closed form, near x = 0. My copy of Abramowitz and Stegun is in softcopy image, and is difficult to search, and 0 as an upper index is problematic. — Arthur Rubin (talk) 19:06, 4 December 2011 (UTC)

Just an fyi, Abramowitz and Stegun is available legally online, including in searchable pdf form. Otherwise, check Hypergeometric function on wiki or Mathworld. I won't help with the problem as that's typically a recipe for stealing my study time for the next two hours. SamuelRiv (talk) 23:44, 4 December 2011 (UTC)

I'm getting

$-{\frac {1}{4}}{}_{2}F_{1}(-{\tfrac {1}{2}},0;{\tfrac {3}{2}};x)=-{\frac {1}{4}}$

$\sum _{n=0}^{\infty }{\frac {1}{(n+{\tfrac {1}{2}})(n-{\tfrac {1}{2}})}}x^{n}={\frac {2(x\tanh ^{-1}({\sqrt {x}})-\tanh ^{-1}({\sqrt {x}})-{\sqrt {x}})}{\sqrt {x}}}=-4+{\frac {4x}{3}}+{\frac {4x^{2}}{15}}+O(x^{3})$

-- Meni Rosenfeld (talk) 09:45, 5 December 2011 (UTC)

That should have been

• $\sum _{n=0}^{\infty }{\frac {1}{(n+{\tfrac {1}{2}})(n-{\tfrac {1}{2}})}}x^{n}=-\mathbf {4} {}_{2}F_{1}(-{\tfrac {1}{2}},\mathbf {1} ;{\tfrac {3}{2}};x)$

and that 1 as an upper index is problematic. I shouldn't post while asleep.

Rewriting your expression, I get

$\sum _{n=0}^{\infty }{\frac {1}{(n+{\tfrac {1}{2}})(n-{\tfrac {1}{2}})}}x^{n}={\frac {2(x\tanh ^{-1}({\sqrt {x}})-\tanh ^{-1}({\sqrt {x}})-{\sqrt {x}})}{\sqrt {x}}}=-2-2(1-x){\frac {\tanh ^{-1}{\sqrt {x}}}{\sqrt {x}}}$

which is exactly what I was looking for, as it also explains why it remains a power series at 0. — Arthur Rubin (talk) 15:33, 5 December 2011 (UTC)

Find point closest to a plane

Hi all,

I am wondering how I can use linear algebra to tackle this problem which was on my midterm:

"Let P denote the plane passing through the points (5, 2, 1), (7, 2, 3), (5, 5, 1). Notice that this plane does not pass through the origin. Find the point on P that is nearest to (10, 10, 10)"

I tried using the least squares solution, i.e. x* = (A^T A)^-1 A^T b where A is the matrix formed by the 3 points that the plane passes through (in columns), and b is (10, 10, 10). Since I ran out of time on the midterm, I only went as far as calculating (A^T A) is. However, the grader crossed out my work completely. Am I at least on the right track? I tried using my GDC at home to calculate this and the answer I got is (-25/3, 5, 10/3).

Is it possible to use other methods to solve this problem other than the least square solution? I thought about Lagrange multipliers, but I'm not sure what my F and G should be. I suppose the function that I want to optimize will be the distance formula d^2 = (x-10)^2 + (y-10)^2 + (z-10)^2 and the constraint would be the equation of the plane (which I have yet to calculate). — Preceding unsigned comment added by 169.232.72.232 (talk) 20:45, 4 December 2011 (UTC)

The point on P closest to (10,10,10) is the point, say p, such that the chord joining p to (10,10,10) is perpendicular to P. The equation of P is x – z = 4. The vector (1,0,–1) is perpendicular to P. For the point on P, closest to (10,10,10), we need to set off from (10,10,10) in the direction (1,0,–1) and see which point we meet P. Consider

$q(\lambda ):=(10,10,10)+\lambda (1,0,-1)=(10+\lambda ,10,10-\lambda )\,.$

The point q(λ) lies on the plane P when x – z = 4, i.e. when

$(10+\lambda )-(10-\lambda )=4\,\implies \lambda =2\,.$

Since q(2) = (12,10,8), I make (12,10,8) the point on P which is closest to (10,10,10). — Fly by Night (talk) 21:33, 4 December 2011 (UTC)

What you were trying to do with the least squares would give you the closest point to P in the 3-dimensional space which includes 0 and is spanned by the 3 vectors. This space is $\mathbb {R} ^{3}$ since the vectors are linearly independent, so what you would get is P itself (and what you denoted by x* is just the coordinates, to get the actual point you need to multiply by A). To use least squares you can translate everything so that the plane does go through the origin, for example by moving (5,2,1) to (0,0,0). Then you get the plane spanned by (2,0,2) and (0,3,0), and the point (5,8,9). Don't forget to translate the result back. -- Meni Rosenfeld (talk) 18:43, 5 December 2011 (UTC)

Searching for patters in a lattice

I've got circles arranged in a closed-packed hexagonal lattice, and the circles are randomly painted black or white. Suppose I wanted to find the number of times that some pattern shows up. Say, a black triangle that's made of rows of 1,2,3 circles. I also don't want the triangles to overlap. Is there an efficient algorithm to do this? --HappyCamper 21:40, 4 December 2011 (UTC)

First, assume you have an algorithm called "Is A Triangle" that, given a circle, returns a true/false result. It return True if the circle is the point of a triangle. Of course, the algorithm can have a size parameter. So, you can give it a circle and 3 and it will return True if the circle is a corner of a 3 line triangle. Given this, finding a triangle of a specific size is easy. Just check every circle and send it to the Is a Triangle algorithm. You will get all the triangles. But, you want to avoid overlap. I assume you are looking for black triangles. So, once you find a triangle, change it to white. The circles used won't be used in any other black triangle because they will now be white. As for the Is a Triangle algorithm - that is rather straightforward. While the triangle may be of a large size, the initial circle must be the corner of the triangle. So, checking neighboring circles is easy. Unfortunately, this whole thing will not give you the maximal solution. Picking out one triangle may omit two others that overlap. -- kainaw™ 22:12, 4 December 2011 (UTC)

I think I want something a little more sophisticated because eventually I want to count things like the number of times a row of 3 black and then 4 white followed by another row of black, white, black circles show up. The brute force approach seems to be to make a matrix to represent the random array of circles, followed by a bunch of checks to ensure that the correct shape is present as the matrix is scanned. But this gets tedious to code once I have lots of patterns I want to try and match. Any other ideas? --HappyCamper 00:52, 5 December 2011 (UTC)

The unsophisticated solution is a step in the direction of finding more sophisticated solutions. Don't optimize until you have got something to optimize. Working out a simple solution will help you understand what you are talking about, and perhaps rephrase the problem. Bo Jacoby (talk) 01:17, 5 December 2011 (UTC).

To put this suggestion another way... You are requesting a specialized form of a pattern matching algorithm. Another, much more common, form of pattern matching is substring searching. For example, I want to find ADA in the string AAAADDDAADADDDAAADDA. Can I do that without checking every position in the string? No. If I never check those three positions that contain ADA, I won't find ADA (unless you have already been told that ADA is certainly in the string - but that is a whole different problem). So, you can brute force it from left to right. You can brute force it from right to left. You can brute force it by splitting it half, then split each half in half, then split those in half, etc... No matter how you do it, you must check every position. So, hopefully, you can see that you have to check your entire lattice to find a sub-lattice in the entire lattice. -- kainaw™ 03:54, 5 December 2011 (UTC)

As I wrote the above, I had an idea for what I think would be a cool research paper... The Wagner-Fischer algorithm can be adapted to find the best alignment of a short string in a long string by initializing the top/left cells of the matrix to zero instead of 1,2,3... The strings are one-dimensional (left to right only). The matrix required to solve it is two-dimensional. What if you are looking for a fuzzy match of a two-dimensional small matrix inside a large matrix? I assume the same algorithm may be used, but the matrix required to solve it must be more than two dimensions. My best guess is it must be four dimensions. Now, your lattice is three-dimensional. Each cell connects in three linear directions. I assume that with a six-dimensional matrix you could perform a fuzzy-match to locate a small lattice in a large lattice. The big problem is runtime. The real Wagner-Fischer algorithm is O(mn) for a short string of length m and a long string of length n. As the dimensions increase, so will the runtime. For a lattice, I expect it to me O(m³n³). But, proving that you can extend fuzzy matches from strings to grids to lattices would be publishable. -- kainaw™ 04:01, 5 December 2011 (UTC)

OK, I think I found a good starting point for what I want: Baker-Bird algorithm which we don't have on Wikipedia yet! --HappyCamper 05:51, 5 December 2011 (UTC)