Mathematics - SciBuff.com

Reflection matrix

June 22, 2009 11:07 by scibuff

It’s been a while since my last math post. It seems that my previous assertion correlating the quality of question with the period of final exams could not have been further from the truth. It now seems quite likely that the occurrence of a few “good” questions on Yahoo Answers in a short period of time a few weeks back was more of a fluke rather than the norm.

Problem: Find the standard matrix for the linear transformation which reflects points in the x-y plane across the line $y = \frac{-2x}{3}$ .

Solution: To find the matrix representing a given linear transformation all we need to do is to figure out where the basis vectors, i.e.

$\vec{e_{1}}=\begin{bmatrix} 1\\ 0 \end{bmatrix}$ and $\vec{e_{2}}=\begin{bmatrix} 0\\ 1 \end{bmatrix}$

are mapped under the transformation.

This is easy to see from the fact that since $\vec{e_{1}}$ and $\vec{e_{2}}$ form a basis of $\mathbb{R}^{2}$ any element

$\vec{u}\ \epsilon \ \mathbb{R}^{2}$

can be written as

$\vec{u} = a \cdot \vec{e_{1}} + b \cdot \vec{e_{2}}$

for some $a,b\ \epsilon\ \mathbb{R}$ .

Now let

$A : \mathbb{R}^{2} \to \mathbb{R}^{2}$

be a linear transformation. Then, by definition

$A(\vec{u}) = A(a \cdot \vec{e_{1}} + b \cdot \vec{e_{2}}) = a \cdot A( \vec{e_{1}} ) + b \cdot A( \vec{e_{2}} )$

Thus, the image of any element $\vec{u}\ \epsilon \ \mathbb{R}^{2}$ under a linear transformation is completely determined by the image of the basis of the transformation’s domain.

Let’s find the image of $\vec{e_{1}}=\begin{bmatrix} 1\\ 0 \end{bmatrix}$ under a reflection across the line given by $y = \frac{-2x}{3}$ . First, we need to find a line perpendicular to $y = \frac{-2x}{3}$ that passed through the point $p_{1} = (1, 0)$ .

In general, a line perpendicular to $y = mx + b$ is given by $y = \frac{-x}{m}$ , i.e in our case, $y = \frac{3x}{2}$ . To find the one particular line with the same slope, that passes through $p_{1} = (1, 0)$ , we need to simply plug in the values of $x = 1$ and $y = 0$ into the line equation and add a constant value so that the equality will hold. Then we have

$(0) = \frac{3(1)}{2}+b$

Thus, the line perpendicular to $y = \frac{-2x}{3}$ that passes through $p_{1} = (1, 0)$ is given by $y = \frac{3x}{2} - \frac{3}{2}$

The lines given by equations (1) - red and (2) - green

Now let’s find the point $q_{1} = (x, y)$ at which our two lines $y = \frac{-2x}{3}$ and $y = \frac{3x}{2} - \frac{3}{2}$ intersect. This is done easily by solving the two line equation simultaneously:

$y = \frac{-2x}{3} \ (1)$

$y = \frac{3x}{2} - \frac{3}{2} \ (2)$

Equating $(1)$ and $(2)$ (and multiplying by 6 for simplicity) gives

$-4x = 9x - 9$

$x = \frac{9}{13}$

which then gives

$y = \frac{-6}{13}$

Thus, our two lines intersect at

$q_{1} = \left (\frac{9}{13}, \frac{-6}{13} \right )$

Now, let ${p_{1}}' = (x, y)$ be the reflection of $p_{1} = (1, 0)$ across $y = \frac{-2x}{3}$ . Since ${p_{1}}'$ and $p_{1}$ are symmetric across $q_{1}$ (because that is how the reflection is actually constructed) it follows that

$x = q_{1}x - \left | p_{1}x - q_{1}x \right | = \frac{9}{13} - \left | 1 - \frac{9}{13} \right | = \frac{5}{13}$

$y = q_{1}y - \left | p_{1}y - q_{1}y \right | = \frac{-6}{13} - \left | 0 - \frac{-6}{13} \right | = \frac{-12}{13}$

$A( \vec{e_{1}} ) = \begin{bmatrix} \frac{5}{13} \\ \frac{-12}{13} \end{bmatrix}$

Similarly as above, we find the image of $\vec{e_{2}}=\begin{bmatrix} 0\\ 1 \end{bmatrix}$ under a reflection across the line given by $y = \frac{-2x}{3}$ . The line perpendicular to $y = \frac{-2x}{3}$ that passed through the point $p_{2} = (0, 1)$ is given by

$y = \frac{3x}{2} + 1 \ (3)$

The lines given by equations (1) - red, (2) - green, and (3) - blue

Equating $(1)$ and $(3)$ (and multiplying by 6 again) gives

$-4x = 9x + 6$

$x = \frac{-6}{13}$

and so

$y = \frac{4}{13}$

Therefore, $(1)$ and $(3)$ intersect at

$q_{2} = \left (\frac{-6}{13}, \frac{4}{13} \right )$

and the image ${p_{2}}' = (x, y)$ of $p_{2} = (0, 1)$ under the reflection across $y = \frac{-2x}{3}$ is given by

$x = q_{2}x - \left | p_{2}x - q_{2}x \right | = \frac{-6}{13} - \left | 0 - \frac{-6}{13} \right | = \frac{-12}{13}$

$y = q_{2}y - \left | p_{2}y - q_{2}y \right | = \frac{4}{13} - \left | 1 - \frac{4}{13} \right | = \frac{-5}{13}$

which yields

$A( \vec{e_{2}} ) = \begin{bmatrix} \frac{-12}{13} \\ \frac{-5}{13} \end{bmatrix}$

Finally, the matrix $A : \mathbb{R}^{2} \to \mathbb{R}^{2}$ for the linear transformation which reflects points in the x-y plane across the line $y = \frac{-2x}{3}$ is given by

$A = \begin{bmatrix} \frac{5}{13} & \frac{-12}{13} \\ \frac{5}{13} & \frac{-5}{13} \end{bmatrix}$

It turns out (although I’m not going to show to derivation here) that in general, the matrix for a linear transformation which reflects points in the x-y plane across an arbitrary line $y = mx + b$ is given by

$A = \begin{bmatrix} cos2\theta & sin2\theta \\ sin2\theta & -cos2\theta \end{bmatrix}$

where $\theta$ is the angle that the line makes with the positive x-axis, i.e

$\theta = arctan(m)$ if $m \geq 0$

and

$\theta = arctan(\left | m \right |) + \frac{\pi }{2}$ if $m < 0$

Tags

linear algebra, linear transformations, matrix, reflection

1 comment »

Common Denominators

June 3, 2009 13:05 by scibuff

In the period of finals ( and studying for finals ) yahoo answers have been flooded with homework and assignment problems 99.9% involve mundane “plug it into a formula” type of solutions. As such, these are of no particular interest to me or for this series. Hopefully, now that most students swapped book for beaches, there will be more interesting questions posted. Meanwhile, here are two short problems I picked some time ago

Problem: Prove that if $p(x)$ is relatively prime to $k(x)$ and $f(x)k(x)\equiv g(x)k(x)\ mod\ p(x)$ ,then

$f(x)\equiv g(x)\ mod\ p(x)$

Solution: Using $f(x)k(x)\equiv g(x)k(x)\ mod\ p(x)$ it follows

$f(x)k(x) - g(x)k(x) = k(x)\left ( f(x) - g(x) \right ) \equiv 0\ mod\ p(x)$

Since $p(x)$ is relatively prime to $k(x)$ we know that

$k(x)\not \equiv 0\ mod \ p(x)$

and it must be true that

$f(x) - g(x) \equiv 0\ mod\ p(x)$

Thus $f(x)\equiv g(x)\ mod\ p(x)$ .

Problem: If $gcd(a,4)=2$ and $gcd(b,4)=2$ prove $gcd(a+b,4)=4$ .

Solution: Since $gcd(a,4)=2$ we know that $a = 2p$ for some $p\ \epsilon\ \mathbb{N}$ . Similarly, $b = 2q$ for some $q\ \epsilon\ \mathbb{N}$ . Notice, that both $p$ and $q$ must be odd. If, lets say, $p$ were even, then $p=2s$ for some $s\ \epsilon\ \mathbb{N}$ . But then $a = 2p=2(2s)=4s$ and so $gcd(a,4)=gcd(4s,4)=4$ .

Using $a = 2p$ and $b = 2q$ we have $a + b = 2( p + q )$ . But since both $p$ and $q$ are odd, their sum is even, i.e.

$p + q = 2t$ for some $t\ \epsilon\ \mathbb{N}$

It now follows that

$a + b = 2( p + q )= 2( 2t ) = 4t$

and so

$gcd(a+b,4)=gcd(4t,4)=4$

Tags

abstract algerba, modular arithmetic, polynomial rings

1 comment »

Even “More” Infinite Sets

May 20, 2009 17:41 by scibuff

In my previous post (you should read it first before continuing here), I wrote about a little bit about infinite sets and how we can get a sense of size for some of them. This time, I will give a solution to a problem which will, together with the previous result, demonstrate that sets with infinitely many elements have a “measure” of size, and that not all infinite sets are “equally” infinite.

Problem: Show set of real numbers between 0 and 1 with decimal representations consisting of 1s or 9s, i.e. $S=\left \{0.1, 0.9, 0.11, 0.99\cdots \right \}$ is uncountable.

Solution: To solve this problem we will use a proof by contradiction just as we did before.

Suppose, that similarly as in the last problem, we can put our $S$ into a one-to-one correspondence with the set of natural numbers $\mathbb{N}=\left \{0, 1, 2, 3,\cdots \right \}$ . In other words, we can create a list of ALL elements in our set (just as we did before) like so:

$0\rightarrow s_{0}$

$1\rightarrow s_{1}$

$2\rightarrow s_{2}$

$\vdots$

Now, consider any such arbitrary listing of the elements of $S$ , for example, this one:

$s_{0}=0.111111\cdots$

$s_{1}=0.999999\cdots$

$s_{2}=0.191919\cdots$

$s_{3}=0.919191\cdots$

For the following argument the order of the elements on the list is irrelevant. The important thing is we have listed them ALL. Now, suppose with create a number $s$ in the following way:

Make the first (decimal) digit of $s$ be different from the first (decimal) digit of $s_{0}$ , i.e. 9
Then make the second (decimal) digit of $s$ be different from the second (decimal) digit of $s_{1}$ , 1
The third (decimal) digit of $s$ to be different from the third (decimal) digit of $s_{2}$ , i.e. 9
The fourth(decimal) digit of $s$ to be different from the fourth (decimal) digit of $s_{3}$ , i.e. 1
etc …

It is relatively easy to show that a number created in such a way as $s$ CANNOT be on our list. If $s$ were on the list then $s = s_{n}$ for some $n\in \mathbb{N}$ . So, in particular, the n-th (decimal) digit of $s$ must be equal to the n-th (decimal) digit of $s_{n}$ . But that is not possible by the very definition of $s$ .

On the other hand, set $S$ is the set of all real numbers between 0 and 1 with decimal representations consisting of 1s or 9s, in particular, $s\in S$ .

The assumption that $S$ is countable led us to conclude that $s\notin S$ and at the same time $s\in S$ , which is impossible. Therefore $S$ must be uncountable.

On a side note: $S$ can actually be put into one-to-one correspondence with the entire set of real numbers (which also true of any open interval of non-zero length)

Tags

aleph, Cantor, infinite set, sets, uncountable

1 comment »

Infinite Sets

May 20, 2009 13:56 by scibuff

I distinctly remember one day in second grade when the day after our first class on multiplication my friend infamously claimed that

$\frac{1}{0}=\infty$

Although he was definitely incorrect in his thinking and reasoning, because division be zero has no meaning when it comes to real numbers (or integers), there are cases, such as The Riemann Sphere or a one-element field where the multiplicative identity coincides with the additive identity, when the equation above is actually true (and well defined).

It is sometimes quite tempting (and even useful) to consider

$\lim_{x\to 0}\frac{1}{x}=\frac{\lim_{x\to 0}1}{\lim_{x\to 0}x}=\frac{1}{0}=\infty$

The main problem with allowing the division by zero is that it results in logical fallacies such as 1=0 (actually, one can equate any two numbers using it). Eventually, mathematicians found a way to define limits rigorously without infinitesimal quantities needed by Newton and Leibnitz when Cauchy and Weierstrass laid down the foundation of modern analysis.

The next question from Yahoo Answers is related to a different kind of infinity – the kind that deals with sets. The works of Georg Cantor between 1874 and 1884 are the origin of set theory in which he established the importance of one-to-one correspondence between sets, defined infinite and well-ordered sets, and proved that the real numbers are “more infinite” than the natural numbers. The diagonalization argument he used demonstrates a powerful and general technique that has since been used in a wide range of proofs such as this one.

Problem: Determine whether the set of real numbers between 0 and 1 with decimal representations consisting of 1s, i.e. $S=\left \{0.1, 0.11, 0.111,\cdots \right \}$ is countable or uncountable?

Definitions:

A function $f:A\rightarrow B$ is bijective if and only if for every $b\in B$ there is exactly one $a\in A$ such that $f(a)=b$
A set $S$ is said to be countable if there exists a bijective function $f:\mathbb{N}\rightarrow S$ where $\mathbb{N}=\left \{0, 1, 2, 3,\cdots \right \}$ is the set of natural numbers.

Solution:

Let us look at set $S=\left \{0.1, 0.11, 0.111,\cdots \right \}$ and consider the following list:

$0:\ 0.1$

$1:\ 0.11$

$2:\ 0.111$

$\vdots$

It is easy to see that our set $S$ can be easily put into a one-to-one correspondence with the set of natural numbers $\mathbb{N}=\left \{0, 1, 2, 3,\cdots \right \}$ , e.g. the correspondence is given by the list (function defined) above.

To be precise, let $f:\mathbb{N}\rightarrow S$ be given by

$f(n)=\overset{k=n}{\underset{k=0}{\sum}}10^{-(k+1)}$

To show that $f$ is bijective, we need to show that for every $s_{n}\in S$ there is exactly one, i.e. a unique, $n\in \mathbb{N}$ such that $f(n)=s_{n}$ .

Consider an arbitrary $s_{m}\in S$ . Since

$s_{m}=0.\overset{m}{\overbrace{111\cdots 111}}$

we have

$s_{m}=0.1+0.01+\cdots+0.\overset{m\ 0s}{\overbrace{000\cdots 000}}1 =10^{-1}+10^{-2}+\cdots + 10^{-(m+1)}$

and so by taking $n=m$ we get

$s_{m}=10^{-1}+10^{-2}+\cdots + 10^{-(m+1)}=\overset{k=m}{\underset{k=0}{\sum}}10^{-(k+1)}=f(m)$

Therefore, for every $s_{n}\in S$ we have proven the existance of (at least one) $n\in \mathbb{N}$ such that $f(n)=s_{n}$ .

To show uniqueness, we need to demonstrate that if $f(n)=f(m)$ then $n=m$ . The easiest way to accomplish this is to use proof by contrapositive, that is, the fact that

$f(n)=f(m)\Rightarrow n=m$

is equivalent to

$n\neq m\Rightarrow f(n)\neq f(m)$

Let $n,m\in \mathbb{N}$ be such that $n\neq m$ . Without loss of generality, assume $n < m$ (otherwise rename them). Then it follows that there exist $l>0:l\in \mathbb{N}$ such that $n=m+l$ . Therefore

$f(n)=f(m+l)$

$f(m+l)=10^{-1}+10^{-2}+\cdots+10^{-m}+10^{-(m+1)}+10^{-(m+2)}+\cdots+10^{-(m+l+1)}$

$f(m+l)=\overset{f(m)}{\overbrace{10^{-1}+10^{-2}+\cdots+10^{-m}+10^{-(m+1)}}}+10^{-(m+2)}+\cdots+10^{-(m+l+1)}$

$f(m+l)=f(m)+10^{-(m+2)}+\cdots+10^{-(m+l+1)}$

$f(m+l)=f(m)+10^{-(m+1)}\overset{f(l-1)}{\overbrace{(10^{-1}+\dots+10^{-l})}}$

$f(m+l)=f(m)+10^{-(m+1)}f(l-1)$

Since $l>0$ it follows that $f(l-1)\geq10^{-1}>0$ and so we have

$f(n)-f(m)=f(m+l)-f(m)=10^{-(m+1)}f(l-1)>0$

$f(n)-f(m)\neq 0$

$f(n)\neq f(m)$

thus proving the uniqueness. Therefore $f:\mathbb{N}\rightarrow S$ is a bijective function and so $S$ is countable.

Tags

calculus, Cantor, Cauchy, countable, division by zero, limits, Riemann sphere, Weierstrass

1 comment »

Found Identity – Order of Group Elements

May 18, 2009 14:34 by scibuff

Another one in my series of Yahoo Answers this time using elementary properties of Groups.

Problem: Let $a,b\ \epsilon\ G$ be elements of group such that $(ab)^{k}=e$ where $e$ is the identity element of $G$ . Prove that $(ba)^{k}=e$

Solution: The problem is indeed trivial if $G$ is abelian, i.e. $ab=ba$ for all $a,b\ \epsilon\ G$ . One must be careful not to assume such properties when dealing with constructs in abstract algebra. Nevertheless, the solution below is quite simple and uses only associativity of Groups, i.e. $(ab)c=a(bc)$ for all $a,b,c\ \epsilon\ G$ .

Lemma: For any $a,b\ \epsilon\ G$ there is a unique $x\ \epsilon\ G$ such that $ax=b$ .

Proof: The lemma can be proven in two steps. First, show that such $x$ exists, and second, show that it must be unique.

Let $x=a^{-1}b$ . Since $a,b\ \epsilon\ G$ and $G$ is a group, it follows from the existence of inverses that $a^{-1}\ \epsilon\ G$ and from group closure $a^{-1}b\ \epsilon\ G$ . Thus, $x\ \epsilon\ G$ (and the first step is done).

Let $x\ \epsilon\ G$ be such that $ax=b$ , take $e$ to be the identity element of $G$ . Then

$x=ex=(a^{-1}a)x=a^{-1}(ax)=a^{-1}b$

Thus it follows that if $ax=b$ then it must be that $x=a^{-1}b$ , finishing the second step, hence proving out lemma.

Now we go back to our proof. Suppose

$(ab)^{k}=e$

is the identity in $G$ , i.e.

$\overset{k\ times}{\overbrace{(ab)(ab)\cdots (ab)}}=e\ (1)$

Using group associativity we get

$a\overset{k-1\ times}{\overbrace{(ba)(ba)\cdots (ba)}}b=a(ba)^{k-1}b=e\ (2)$

“Multiplying” $(2)$ by $a$ (on right) we get

$a(ba)^{k-1}ba=a(ba)^{k}=ea$

$a(ba)^{k}=a\ (3)$

Now multiplying $(2)$ by $b$ (on left) we get

$ba(ba)^{k-1}b=(ba)^{k}b=be$

$(ba)^{k}b=b\ (4)$

Now from $(3)$ we have

$ba(ba)^{k}=ba\ (5)$

and from $(4)$

$(ba)^{k}ba=ba\ (6)$

Combining $(5)$ and $(6)$

$ba(ba)^{k}=(ba)^{k}ba=ba\ (7)$

Since $e$ is the identity element of $G$ , by definition

$(ba)e=e(ba)=ba\ (8)$

Finally, using our Lemma and $(7)$ with $(8)$ it follows that $(ba)^{k}=e$

Tags

abelian group, abstract algebra, group, identity, inverse

No comments »

Golden Nature: Closed-form Formula for Fibonacci Sequence

May 13, 2009 13:56 by scibuff

Almost everyone has heard of this sequence: $1,\ 1,\ 2,\ 3,\ 5,\ 8,\ etc$ . It is named after Leonardo of Pisa who introduced it to the western world in one of the most influential books ever published in mathematics – Liber Abaci. This book introduced Europe to the Hindu numerals 0 through 9, the word zero, the notion of an algorithm and the subject of algebra.

The beauty of the Fibonacci sequence and the golden ratio (which is intimately connected to it) lies in that they are not just another mathematical construct, but occur throughout the nature.

Have you ever taken a look at a pine cone and noticed that the scales of the cone are in spirals? Have you ever counted the spiral in the clockwise and counterclockwise directions? I would be surprised if you have … but the counts turn out to be 5 and 8 (or 8 and 13 for bigger cones).

Pine Cone Spirals

How about these? Care to count the petals?

13 petals

21 petals

… intriguing stuff indeed.

So, once again, I was reading through problems on Yahoo Answers. Most of the questions “reduce” (lol) to plugging numbers into well known equations, or using a calculator such as TI-89, or Mathematics, Maple, or even Google – basically, what engineers do. Yeah, you “heard” me right! It takes some effort to found a meaningful question that actually requires some knowledge and skills – see the difference between a mathematician and an engineer now? That said, here’s a one I couldn’t resist:

Problem: Find the term $F_{386}$ in the following sequence $F_{0}=-4,\ F_{1}=5,\ F_{2}=1,\ F_{3}=6,\ F_{4}=7,\ F_{5}=13$

There is a more “elegant” way to tackle this problem and I may write about in the future (maybe quite soon actually), but for now I’ll ignore matrices, diagonalization and eigenspaces (although the reason why the following solution gives the correct result is tightly connected to linear algebra) and focus, instead, on the recursive nature of the Fibonacci sequence.

Solution: To find the term, “all” that is needed is to find the closed form for the n-th terms of the sequence $F_{n}$ . In general, a Fibonacci sequence is given by

$F_{n} = F_{n-1} + F_{n-2}\ (1)$

and any particular sequence is fully determined by the initial two terms

$F_{0}$ and $F_{1}$

In our example, we have

$F_{0}=-4$ and $F_{1}=5$

To find the closed form, let’s assume

$F_{n}=(-4)\times t^{n}$

Then using our recursive formula $(1)$ we get

$(-4)t^{n+1}=(-4)\left ( t^{n} + t^{n-1}\right )$

and so

$t^{2}=t + 1\Rightarrow t^{2} - t - 1 = 0\ (2)$

Solving the quadratic from $(2)$ gives

$t_{1,2}=\frac{1\pm \sqrt{5}}{2}$

Using this result, we can write the closed form formula for the n-th term of our sequence as

$F_{n}=-4\left ( \ C_{1}\left ( \frac{1+\sqrt{5}}{2} \right )^{n}+C_{2}\left ( \frac{1-\sqrt{5}}{2} \right )^{n}\ \right ) (3)$

where $C_{1}$ and $C_{2}$ are constant parameters determined by our initial conditions,

$F_{0}=-4$ and $F_{1}=5$

We can calculate these values by solving the following system of equations

$F_{0} = -4\times t^{0}=-4 \left ( C_{1}\times t_{1}^{0} + C_{2}\times t_{2}^{0} \right )$

$F_{1} = -4\times t^{1}=-4 \left ( C_{1}\times t_{1}^{1} + C_{2}\times t_{2}^{1} \right )$

Plugging in known values gives us

$-4 = -4 \left (C_{1} \left ( \frac{1+\sqrt{5}}{2} \right )^{0} + C_{2} \left ( \frac{1-\sqrt{5}}{2} \right )^{0} \right )$

$5 = -4 \left (C_{1} \left ( \frac{1+\sqrt{5}}{2} \right )^{1} + C_{2} \left ( \frac{1-\sqrt{5}}{2} \right )^{1} \right )$

Simplifying turns the above into

$1 = C_{1} \left ( \frac{1+\sqrt{5}}{2} \right )^{0} + C_{2} \left ( \frac{1-\sqrt{5}}{2} \right )^{0} = C_{1} + C_{2} \ (4)$

$\frac{-5}{4} = C_{1} \left ( \frac{1+\sqrt{5}}{2} \right ) + C_{2} \left ( \frac{1-\sqrt{5}}{2} \right ) \ (5)$

Now we need to solve $(4)$ and $(5)$ for $C_{1}$ and $C_{2}$ . Although I said I was going to leave matrices alone, this is a perfect situation to use them. I prefer to use the procedure described below for a system of two equations with coefficients such as these. Substitution or elimination method would, of course, work, but they involves messy arithmetic which can be so easily error prone in situations such as this one.

We have the following system:

$\begin{pmatrix} 1 & 1 \\ \frac{1+\sqrt{5}}{2} & \frac{1-\sqrt{5}}{2} \end{pmatrix} \begin{pmatrix}C_{1}\\ C_{2}\end{pmatrix} = \begin{pmatrix}1\\ \frac{-5}{4}\end{pmatrix}\ (6)$

In general, to solve the equation

$Au=v$

we use

$A^{-1}Au=A^{-1}v$

which turns into

$u=A^{-1}v$

Hence, to solve $(6)$ we need to find the inverse of our matrix. This is fairly simple for a 2 by 2 matrix … Let

$A=\begin{pmatrix}a & b\\ c & d\end{pmatrix}$

then

$A^{-1}=\frac{1}{ad-bc}\begin{pmatrix}d & -b\\ -c & a\end{pmatrix}$

and so

$\begin{pmatrix} 1 & 1 \\ \frac{1+\sqrt{5}}{2} & \frac{1-\sqrt{5}}{2} \end{pmatrix}^{-1} =\frac{-1}{\sqrt{5}}\begin{pmatrix} \frac{1-\sqrt{5}}{2} & -1 \\ \frac{-1-\sqrt{5}}{2} & 1 \end{pmatrix}$

Our equation $(6)$ then becomes

$\begin{pmatrix} 1 & 1 \\ \frac{1+\sqrt{5}}{2} & \frac{1-\sqrt{5}}{2} \end{pmatrix}^{-1}\begin{pmatrix} 1 & 1 \\ \frac{1+\sqrt{5}}{2} & \frac{1-\sqrt{5}}{2} \end{pmatrix} \begin{pmatrix}C_{1}\\ C_{2}\end{pmatrix} = \begin{pmatrix} 1 & 1 \\ \frac{1+\sqrt{5}}{2} & \frac{1-\sqrt{5}}{2} \end{pmatrix}^{-1} \begin{pmatrix}1\\ \frac{-5}{4}\end{pmatrix}$

$\begin{pmatrix}C_{1}\\ C_{2}\end{pmatrix} = \frac{-1}{\sqrt{5}}\begin{pmatrix} \frac{1-\sqrt{5}}{2} & -1 \\ \frac{-1-\sqrt{5}}{2} & 1 \end{pmatrix} \begin{pmatrix}1\\ \frac{-5}{4}\end{pmatrix}$

which gives us

$C_{1}=\frac{-2(1-\sqrt{5})-5}{4\sqrt{5}}\ (7)$

$C_{2}=\frac{2(1+\sqrt{5})+5}{4\sqrt{5}}\ (8)$

Finally, by plugging $(7)$ and $(8)$ into $(3)$ we get

$F_{n}=-4\left (\left ( \frac{-2(1-\sqrt{5})-5}{4\sqrt{5}} \right )\left ( \frac{1+\sqrt{5}}{2} \right )^{n}+\left ( \frac{2(1+\sqrt{5})+5}{4\sqrt{5}} \right )\left ( \frac{1-\sqrt{5}}{2} \right )^{n}\right ) (9)$

We can now “easily” compute $F_{386}$ which is given by

$F_{386}=-4\left (\left ( \frac{-2(1-\sqrt{5})-5}{4\sqrt{5}} \right )\left ( \frac{1+\sqrt{5}}{2} \right )^{386}+\left ( \frac{2(1+\sqrt{5})+5}{4\sqrt{5}} \right )\left ( \frac{1-\sqrt{5}}{2} \right )^{386}\right )$

Google returns $F_{386} \cong 5.2783459\times 10^{80}$ which is just an approximation, but now we have a formula for the precise answer.

If you wish to check for yourself that out formula $(9)$ is indeed correct, click on the terms below to see the computation by Google:

On a side note – Raising a number to the power of 386 may seem like a long computation but it really requires only 10 multiplications! Don’t believe me?

Consider this:

$\left ( \frac{1+\sqrt{5}}{2} \right )^{386}=\left ( \frac{1+\sqrt{5}}{2} \right )^{256}\left ( \frac{1+\sqrt{5}}{2} \right )^{128}\left ( \frac{1+\sqrt{5}}{2} \right )^{2}$

To calculate

$\left ( \frac{1+\sqrt{5}}{2} \right )^{256}$

we use the fact that

$1.)\ \left ( \frac{1+\sqrt{5}}{2} \right )^{2} = \left ( \frac{1+\sqrt{5}}{2} \right )\left ( \frac{1+\sqrt{5}}{2} \right )$

$2.)\ \left ( \frac{1+\sqrt{5}}{2} \right )^{4} = \left ( \frac{1+\sqrt{5}}{2} \right )^{2} \left ( \frac{1+\sqrt{5}}{2} \right )^{2}$

$3.)\ \left ( \frac{1+\sqrt{5}}{2} \right )^{8} = \left ( \frac{1+\sqrt{5}}{2} \right )^{4} \left ( \frac{1+\sqrt{5}}{2} \right )^{4}$

…

$8.)\ \left ( \frac{1+\sqrt{5}}{2} \right )^{256} = \left ( \frac{1+\sqrt{5}}{2} \right )^{128} \left ( \frac{1+\sqrt{5}}{2} \right )^{128}$

As you can see, in every step (multiplication) we use the result from the previous one and so it takes only 8 steps (multiplications) to calculate

$\left ( \frac{1+\sqrt{5}}{2} \right )^{256}$

Finally, in the process of calculating

$\left ( \frac{1+\sqrt{5}}{2} \right )^{256}$

we get

$\left ( \frac{1+\sqrt{5}}{2} \right )^{128}$ and $\left ( \frac{1+\sqrt{5}}{2} \right )^{2}$

as a bonus, and so to calculate

$\left ( \frac{1+\sqrt{5}}{2} \right )^{386}$

we now only need to use two more multiplications

$\left ( \frac{1+\sqrt{5}}{2} \right )^{386}=\left ( \frac{1+\sqrt{5}}{2} \right )^{256}\left ( \frac{1+\sqrt{5}}{2} \right )^{128}\left ( \frac{1+\sqrt{5}}{2} \right )^{2}$

This idea can be generalized to any

$x\epsilon \Re$

The (maximal) number of multiplications required to compute

$x^{n}\ where\ 2^{p}<n\leq 2^{p+1} \ :n,p\ \epsilon \ N$

is given by

$p+(p+1) = 2p + 1$

To put this result in a little bit of perspective, consider

$x = 2^{43112609}-1$

This number is the currently largest known (Mersenne) prime. It has 12,978,189 digits! But $log_{2}(43112609)\cong 25.36$ and so

$2^{25}< 43112609\leq2^{26}$

It follows that we can calculate

$2^{43112609}-1$

using at most 51 multiplications! Incredible!

Tags

closed-form, diagonalization, eigenspaces, fibonacci, golden ratio, matrix, mersenne prime

No comments »

SciBuff.com

Science Blog

Reflection matrix

Common Denominators

Even “More” Infinite Sets

Infinite Sets

Found Identity – Order of Group Elements

Golden Nature: Closed-form Formula for Fibonacci Sequence

Galaxy Zoo

Latest Posts

Categories

Popular Posts

Most Commented

Most Views

Archive

Blogroll

Social Networks