**66**Comments January 13, 2010

# Using Fibonacci Numbers to Convert from Miles to Kilometers and Vice Versa

I learned an interesting fact about Fibonacci numbers recently while watching a lecture on number theory. Fibonacci numbers can be used to approximately convert from miles to kilometers and back.

Here is how.

Take two consecutive Fibonacci numbers, for example 5 and 8. And you're done converting. No kidding – there are 8 kilometers in 5 miles. To convert back just read the result from the other end - there are 5 miles in 8 km!

Another example. Let's take the consecutive Fibonacci numbers 21 and 34. What this tells us is that there are approximately 34 km in 21 miles and vice versa. (The exact answer is 33.79 km.)

If you need to convert a number that is not a Fibonacci number, just express the original number as a sum of Fibonacci numbers and do the conversion for each Fibonacci number separately.

For example, how many kilometers are there in 100 miles? Number 100 can be expressed as a sum of Fibonacci numbers 89 + 8 + 3. Now, the Fibonacci number following 89 is 144, the Fibonacci number following 8 is 13 and the Fibonacci number following 3 is 5. Therefore the answer is 144 + 13 + 5 = 162 kilometers in 100 miles. This is less than 1% off from the precise answer, which is 160.93 km.

Another example, how many miles are there in 400 km? Well, 400 is 377 + 21 + 2. Since we are going the opposite way now from miles to km, we need the preceding Fibonacci numbers. They are 233, 13 and 1. Therefore there are 233 + 13 + 1 = 247 miles in 400 km. (The correct answer is 248.55 miles.)

Just remember that if you need to convert from km to miles, you need to find the preceding Fibonacci number. But if you need to convert from miles to km, you need the subsequent Fibonacci number.

If the distance you're converting can be expressed as a single Fibonacci number, then for numbers greater than 21 the error is always around 0.5%. However, if the distance needs to be composed as a sum of `n`

Fibonacci numbers, then the error will be around sqrt(n)·0.5%.

**Here's why it works.**

Fibonacci numbers have a property that the ratio of two consecutive numbers tends to the Golden ratio as numbers get bigger and bigger. The Golden ratio is a number and it happens to be approximately 1.618.

Coincidentally, there are 1.609 kilometers in a mile, which is within 0.5% of the Golden ratio.

Now that we know these two key facts, we can figure out how to do the conversion. If we take two consecutive Fibonacci numbers, F_{n+1} and F_{n}, we know that their ratio F_{n+1}/F_{n} is approximately 1.618. Since the ratio is also almost the same as kilometers per mile, we can write F_{n+1}/F_{n} = [mile]/[km]. It follows that F_{n}·[mile] = F_{n+1}·[km], which translates to English as "n-th Fibonacci number in miles is the same as (n+1)-th Fibonacci number in kilometers".

That's all there is to it. A pure coincidence that the Golden ratio is almost the same as kilometers in a mile.

**20**Comments January 07, 2010

# Famous Perl One-Liners Explained, Part IV: String and Array Creation

This is the fourth part of a nine-part article on **famous Perl one-liners**. In this part I will create various one-liners for **string and array creation**. See part one for introduction of the series.

Famous Perl one-liners is my attempt to create "**perl1line.txt**" that is similar to "awk1line.txt" and "sed1line.txt" that have been so popular among Awk and Sed programmers.

The article on famous Perl one-liners will consist of nine parts:

- Part I: File spacing.
- Part II: Line numbering.
- Part III: Calculations.
**Part IV: String creation and array creation (this part).**- Part V: Text conversion and substitution.
- Part VI: Selective printing and deleting of certain lines.
- Part VII: Handy regular expressions.
- Part VIII: Release of perl1line.txt.
- Part IX: Release of Perl One-Liners e-book.

I decided that there will be two new parts in this series. The most powerful feature in Perl is its regular expressions, therefore I will write a part on "**Handy Perl regular expressions**." I also decided to **publish an e-book** after I am done with the series, so that will be the last part of this series. Subscribe to my blog to know when that happens!

**Awesome news:** I have written an e-book based on this article series. Check it out:

I also updated the previous part on calculations with 14 new one-liners on finding values of constants pi and e, doing date calculations, finding factorial, greatest common divisor, least common multiple, generating random numbers, generating permutations, finding power sets and doing some IP address conversions.

Here are today's one-liners:

## String Creation and Array Creation

**49. Generate and print the alphabet.**

perl -le 'print a..z'

This one-liner prints all the letters from a to z as `abcdefghijklmnopqrstuvwxyz`

. The letters are generated by the range operator `..`

. The range operator, when used in the list context (which is forced here by `print`

) on strings, uses the magical auto-increment algorithm that advances the string to the next character. So in this one-liner the auto-increment algorithm on the range `a..z`

produces all the letters from a to z.

I really golfed this one-liner. If you used `strict`

it would not work because of barewords `a`

and `z`

. Semantically more correct version is this:

perl -le 'print ("a".."z")'

Remember that the range operator `..`

produced a list of values. If you wish, you may print them comma separated by setting the `$,`

special variable:

perl -le '$, = ","; print ("a".."z")'

There are many more special variables. Take a look at my special variable cheat sheet for a complete listing.

Syntactically more appealing is to use join to separate the list with a comma:

perl -le 'print join ",", ("a".."z")'

Here the list `a..z`

gets joined by a comma before printing.

**50. Generate and print all the strings from "a" to "zz".**

perl -le 'print ("a".."zz")'

Here the range operator `..`

is used again. This time it does not stop at "z" as in the previous one-liner, but advances z by one-character producing "aa", then it keeps going, producing "ab", "ac", ..., until it hits "az". At this point it advances the string to "ba", continues with "bb", "bc", ..., until it reaches "zz".

Similarly, you may generate all strings from "aa" to "zz" by:

perl -le 'print "aa".."zz"'

Here it goes like "aa", "ab", ..., "az", "ba", "bb", ..., "bz", "ca", ... "zz".

**51. Create a hex lookup table.**

@hex = (0..9, "a".."f")

Here the array `@hex`

gets filled with values `0, 1, 2, 3, 4, 5, 6, 7, 8, 9`

and letters `a, b, c, d, e, f`

.

You may use this array to convert a number (in variable `$num`

) from decimal to hex using base conversion formula:

perl -le '$num = 255; @hex = (0..9, "a".."f"); while ($num) { $s = $hex[($num%16)&15].$s; $num = int $num/16 } print $s'

Surely, much easier way to convert a number to hex is just using the `printf`

function (or `sprintf`

function) with `%x`

format specifier. (The example above just illustrates a use of a hex lookup table that we created by using the range operator.)

perl -le '$hex = sprintf("%x", 255); print $hex'

(See my Perl printf and sprintf format cheat sheet for all the format specifiers.)

To convert the number back from hex to dec use the `hex`

function:

perl -le '$num = "ff"; print hex $num'

The `hex`

function takes a hex string (beginning with or without "0x") and converts it to decimal.

**52. Generate a random 8 character password.**

perl -le 'print map { ("a".."z")[rand 26] } 1..8'

Here the map function executes `("a".."z")[rand 26]`

code 8 times (because it iterates over the dummy range `1..8`

). In each iteration the code chooses a random letter from the alphabet. When `map`

is done iterating, it returns the generated list of characters and `print`

function prints it out by concatenating all the characters together.

If you also wish to include numbers in the password, add `0..9`

to the list of characters to choose from and change `26`

to `36`

as there are 36 different characters to choose from:

perl -le 'print map { ("a".."z", 0..9)[rand 36] } 1..8'

If you need a longer password, change `1..8`

to `1..20`

to generate a 20 character long password.

**53. Create a string of specific length.**

perl -le 'print "a"x50'

Operator `x`

is the repetition operator. This one-liner creates a string of 50 letters "a" and prints it.

If the repetition operator is used in list context, it creates a list (instead of scalar) with the given elements repeated:

perl -le '@list = (1,2)x20; print "@list"'

This one liner creates a list of twenty repetitions of (1, 2) (it looks like (1, 2, 1, 2, 1, 2, ...)).

**54. Create an array from a string.**

@months = split ' ', "Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec"

Here the `@months`

gets filled with values from the string containing month names. As each month name is separated by a space, the `split`

function splits them and puts them in `@months`

. This way `$months[0]`

contains "Jan", `$months[1]`

contains "Feb", ..., and `$months[11]`

contains "Dec".

Another way to do the same is by using `qw//`

operator:

@months = qw/Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec/

The `qw//`

operator takes a space separated string and creates an array with each word being an array element.

**55. Create a string from an array.**

@stuff = ("hello", 0..9, "world"); $string = join '-', @stuff

Here the values in array `@stuff`

get turned in a string `$string`

that has them separated by a hyphen. Turning an array in a string was done by the `join`

function that takes a separator and a list, and concatenates the items in the list in a single string, separated by the separator.

**56. Find the numeric values for characters in the string.**

perl -le 'print join ", ", map { ord } split //, "hello world"'

This one-liner takes the string "hello world", splits it into a list of characters by `split //, "hello world"`

, then it `map`

s the `ord`

function onto each of the characters, which returns the numeric, native 8-bit encoding (like ASCII or EBCDIC) of the character. Finally all the numeric values get joined together by a comma and get printed out.

Another way to do the same is use the `unpack`

function and specify `C*`

as the unpacking template (C means unsigned character and * means as many characters there are):

perl -le 'print join ", ", unpack("C*", "hello world")'

**57. Convert a list of numeric ASCII values into a string.**

perl -le '@ascii = (99, 111, 100, 105, 110, 103); print pack("C*", @ascii)'

Just as we unpacked a string into a list of values with the `C*`

template in the one-liner above, we can pack them back into a string.

Another way to do the same is use the `chr`

function that takes the code point value and returns the corresponding character:

perl -le '@ascii = (99, 111, 100, 105, 110, 103); print map { chr } @ascii'

Similar to one-liner #55 above, function `chr`

gets mapped onto each value in the `@ascii`

producing the characters.

**58. Generate an array with odd numbers from 1 to 100.**

perl -le '@odd = grep {$_ % 2 == 1} 1..100; print "@odd"'

This one-liner generates an array of odd numbers from 1 to 99 (as 1, 3, 5, 7, 9, 11, ..., 99). It uses the `grep`

function that evaluates the given code `$_ % 2 == 1`

for each element in the given list `1..100`

and returns only the elements that had the code evaluate to true. In this case the code tests if the reminder of the number is 1. If it is, the number is odd and it has to be put in the `@odd`

array.

Another way to write is by remembering that odd numbers have the low-bit set and testing this fact:

perl -le '@odd = grep { $_ & 1 } 1..100; print "@odd"'

Expression `$_ & 1`

isolates the low-bit, and grep selects only the numbers with low-bit set (odd numbers).

See my explanation of bit-hacks for full explanation and other related bit-hacks.

**59. Generate an array with even numbers from 1 to 100.**

perl -le '@even = grep {$_ % 2 == 0} 1..100; print "@even"'

This is almost the same as the previous one-liner, except the condition `grep`

tests for is "is the number even (reminder dividing by 2 is zero)?"

**60. Find the length of the string.**

perl -le 'print length "one-liners are great"'

Just for completeness, the `length`

subroutine finds the length of the string.

**61. Find the number of elements in an array.**

perl -le '@array = ("a".."z"); print scalar @array'

Evaluating an array in a scalar context returns the number of elements in it.

Another way to do the same is by adding one to the last index of the array:

perl -le '@array = ("a".."z"); print $#array + 1'

Here `$#array`

returns the last index in array `@array`

. Since it's a number one less than the number of elements, we add 1 to the result to find the total number of elements in the array.

## Perl one-liners explained e-book

I've now written the "Perl One-Liners Explained" e-book based on this article series. I went through all the one-liners, improved explanations, fixed mistakes and typos, added a bunch of new one-liners, added an introduction to Perl one-liners and a new chapter on Perl's special variables. Please take a look:

## Have Fun!

Have fun with these one-liners for now. The next part is going to be about text conversion and substitution.

**Can you think of other string creating and array creation one-liners that I didn't include here?**

This is the fourth post in an article series about MIT's course "Linear Algebra". In this post I will review lecture four on **factorizing** a matrix A into a product of a **lower-triangular** matrix L and an **upper-triangular** matrix U, or in other words A=LU. The lecture also shows how to find the **inverse of matrix product** A·B, how to find the **inverse of transposed matrix** A^{T}, and introduces **permutation matrices**.

Here are the previous lectures:

- Lecture 1: Geometry of Linear Equations
- Lecture 2: Elimination with Matrices
- Lecture 3: Matrix Multiplication and Inverse Matrices

## Lecture 4: A=LU Factorization

Lecture four starts with a small review of inverse matrices. Remember from previous lecture that the inverse of matrix A is matrix A^{-1} such that multiplying them together A·A^{-1} produces the identity matrix I.

Another key fact to remember is that matrix multiplication is associative (can change parenthesis) and that for square matrices the right-inverse is also the left-inverse A·A^{-1} = A^{-1}·A = I.

Lecture then continues with finding the inverse of matrix product A·B. The answer is found by reasoning what should we multiply A·B to get the identity matrix. Let's try B^{-1}·A^{-1}. If this is the inverse of A·B, then multiplying it with A·B from the left and right sides should produce the identity matrix I. Let's test this.

From the right side: (A·B)·(B^{-1}·A^{-1}). Since we can rearrange parenthesis, this is the same as A·(B·B^{-1})·A^{-1}. But B·B^{-1} is identity, therefore A·(B·B^{-1})·A^{-1} = A·I·A^{-1} = A·A^{-1} = I. Seems good so far.

Now the left side: (B^{-1}·A^{-1})·(A·B). We rearrange parenthesis again, B^{-1}·(A^{-1}·A)·B and just like in the previous example, A^{-1}·A is identity and B^{-1}·I·B is B^{-1}·B = I.

We have found the inverse of (A·B). It's (B^{-1}·A^{-1}).

Next, while we're at it, the lecture continues with finding the inverse of transposed matrix A^{T}. It's found by reasoning again. Let's first look at the equation A·A^{-1} = I. We can transpose both sides of this equation and it will still hold. If we transpose the right side, we get the same identity matrix I, because I^{T}=I. But what about the left-hand side? Transposing the left-hand side we get (A·A^{-1})^{T} = (A^{-1})^{T}·A^{T}. Now left-hand side is still equal to right-hand side, therefore (A^{-1})^{T}·A^{T} = I. But from this equation it's instantly obvious that the inverse of A^{T} is (A^{-1})^{T}.

We can therefore note and remember that (A^{T})^{-1} = (A^{-1})^{T}.

Finally the lecture moves on to today's key topic of **A=LU decomposition**. As usual, the topic is introduced by an example.

Let's take a look at this 2x2 matrix A:

And let's try to find the elementary matrix E_{21} that will eliminate the element at row 2, column 1. Multiplying the first row by 4 and subtracting it from the second row will produce a zero at 2, 1.

But look at the right-hand side. It's the **upper-triangular matrix** U (all elements below the diagonal are 0) that we were looking for!

Now if we multiply both sides by the inverse of E_{21}, we get (E_{21})^{-1}·E_{21}·A = (E_{21})^{-1}·U. But (E_{21})^{-1}·E_{21} is identity, therefore A = (E_{21})^{-1}·U. From this equation it's instantly obvious that the **lower-triangular matrix** L is nothing else but (E_{21})^{-1}!

Another form of factorization is A = LDU, where D is the diagonal matrix that contains the pivots. For this example it would be:

Now imagine that we have some arbitrary 3x3 matrix A. To reduce matrix A into upper-triangular matrix U, we first eliminate the element at position 2,1, that is, we multiply A (from the left side) with elimination matrix E_{21}. Then we eliminate the element at 3,1 by multiplying (from the left side) with elimination matrix E_{31}. Finally we eliminate the element at 3,2 by multiplying with elimination matrix E_{32}:

E_{32}·E_{31}·E_{21}·A = U

It follows from this equation that the lower-triangular matrix is the inverse of E_{32}·E_{31}·E_{21}, that is,

L = (E_{32}·E_{31}·E_{21})^{-1} = E_{21}^{-1}·E_{31}^{-1}·E_{32}^{-1}

We have found the factorization of a 3x3 matrix:

A = E_{21}^{-1}·E_{31}^{-1}·E_{32}^{-1}·U = L·U

The algorithm for finding matrices L and U should now be clear. First do the elimination to find matrix U, then invert the product of elimination matrices used for finding U to find L. Actually it's even easier, you don't even need to keep elimination matrices E, or find their inverse. You can just keep the multipliers used in each elimination step. Please see the video to find out how it works.

Next, the cost of elimination algorithm is discussed. How many steps does it take to go from matrix A to U? Turns out the elimination is O(n^{3}) process (more carefully, it takes around n^{3}/3 steps). (See my notes on MIT's Introduction to Algorithms for more info about O-notation.)

Since we sometimes need to do row exchanged to do elimination, the last ten minutes of lecture are spent on permutation matrices. Remember from lecture two that multiplying a matrix from the left side with a permutation matrix exchanges its rows.

The key facts about permutation matrices P are:

- The inverse of P is its transpose: P
^{-1}= P^{T}. - There are n! permutation matrices for n
_{x}n matrices.

Here is the video of the fourth lecture:

Direct link: http://www.youtube.com/watch?v=5hO3MrzPa0A

Topics covered in lecture four:

- [01:20] What is the inverse of A·B?
- [05:20] What is the inverse of A
^{T}? - [09:20] A=LU factorization for 2x2 matrices.
- [13:20] A=LDU factorization.
- [14:50] A=LU decomposition for 3x3 matrices.
- [18:30] Why is finding matrix L trivial?
- [27:25] How many operations does elimination take?
- [42:20] Permutation matrices.
- [47:20] What is the inverse of a permutation matrix?
- [48:20] How many P matrices for 3x3 and 4x4 matrices?

Here are my notes of lecture four:

Have fun with this lecture! The next post is going to be about transpose matrices, symmetric matrices, vector spaces, their subspaces and column spaces of matrices.

PS. This course is taught from Introduction to Linear Algebra textbook. Get it here:

This is the third post in the article series about Unix and Linux utilities that you should know about. In this post I will take you through the useful **lsof** tool. If netcat was called the Swiss Army Knife of Network Connections, then I'd call lsof the **Swiss Army Knife of Unix debugging**.

Lsof follows Unix philosophy closely. It does just one task and it does it perfectly -- it lists information about files opened by processes. An open file may be a regular file, a directory, a NFS file, a block special file, a character special file, a shared library, a regular pipe, a named pipe, a symbolic link, a socket stream, an Internet socket, a UNIX domain socket, and many others. Since almost everything in Unix is a file, you can imagine how incredibly useful lsof is!

See the first post on pipe viewer for the introduction to this article series. If you are interested in articles like this one, I suggest that you subscribe to my rss feed to receive my future posts automatically!

## How to use lsof?

In this article I will try to present lsof based on as many use cases as I can think of. Let's start with the simplest (that you probably already know) and proceed to more complicated ones.

## List all open files.

# lsof

Running `lsof`

without any arguments lists all open files by all processes.

## Find who's using a file.

# lsof /path/to/file

With an argument of a path to a file, lsof lists all the processes, which are using the file in some way.

You may also specify several files, which lists all the processes, which are using all the files:

# lsof /path/to/file1 /path/to/file2

## Find all open files in a directory recursively.

# lsof +D /usr/lib

With the `+D`

argument lsof finds all files in the specified directory and all the subdirectories.

Note that it's slower than the usual version with `grep`

:

# lsof | grep '/usr/lib'

It's slower because `+D`

first finds all the files and only then does the output.

## List all open files by a user.

# lsof -u pkrumins

The `-u`

option (think **u**ser) limits output of files opened only by user **pkrumins**.

You can use comma separated list of values to list files open by several users:

# lsof -u rms,root

This will list all the files that are open by users **rms** and **root**.

Another way to do the same is by using the `-u`

option twice:

# lsof -u rms -u root

## Find all open files by program's name.

# lsof -c apache

The `-c`

option selects the listing of files for processes whose name begins with **apache**.

So instead of writing:

# lsof | grep foo

You can now write the shorter version:

# lsof -c foo

In fact, you can specify just the beginning part of the process name you're looking for:

# lsof -c apa

This will list all the open files by a processes whose starts with **apa**.

You can also specify several `-c`

options to output open files by several processes:

# lsof -c apache -c python

This will list all open files by **apache** and **python**.

## List all open files by a user OR process.

# lsof -u pkrumins -c apache

Lsof options can be combined. The default is to OR between options. It means it will combine outputs of `-u pkrumins`

and `-c apache`

producing a listing of all open files by **pkrumins** and all open files by **apache**.

## List all open files by a user AND process.

# lsof -a -u pkrumins -c bash

Notice the `-a`

option. It combines the options with AND. The output listing is files opened by **bash**, which is run under **pkrumins** user.

## List all open files by all users EXCEPT root.

# lsof -u ^root

Notice the `^`

character before **root** username. It negates the match and causes lsof print all open files by all users who are not root.

## List all open files by the process with PID.

# lsof -p 1

The `-p`

option (think **P**ID) filters out open files by program's id.

Remember that you can select multiple PIDs by either comma separating the list or using multiple `-p`

arguments:

# lsof -p 450,980,333

This selects processes with PIDs 450, 980 and 333.

## List all open files by all the processes EXCEPT process with PID.

# lsof -p ^1

Here the negation operator `^`

is used again. It inverts the list and does not include process with PID 1.

## List all network connections.

# lsof -i

Lsof with `-i`

option lists all processes with open Internet sockets (TCP and UDP).

## List all TCP network connections.

# lsof -i tcp

The `-i`

argument can take several options, one of them is `tcp`

. The `tcp`

option forces lsof to list only processes with TCP sockets.

## List all UDP network connections.

# lsof -i udp

The `udp`

option causes lsof to list processes with UDP sockets.

## Find who's using a port.

# lsof -i :25

The `:25`

option to `-i`

makes lsof find processes using TCP or UDP port 25.

You may also use service port name (found in `/etc/services`

) rather than port number:

# lsof -i :smtp

## Find who's using a specific UDP port.

# lsof -i udp:53

Similarly, to find who's using a TCP port, use:

# lsof -i tcp:80

## Find all network activity by user.

# lsof -a -u hacker -i

Here the `-a`

option combines `-u`

and `-i`

to produce listing of network file usage by user **hacker**.

## List all NFS (Network File System) files.

# lsof -N

This option is easy to remember because `-N`

is **N**FS.

## List all Unix domain socket files.

# lsof -U

This option is also easy to remember because `-U`

is **U**nix.

## List all files for processes with a specific group id.

# lsof -g 1234

Process groups are used to logically group processes. This example finds all files opened by processes with PGID `1234`

.

## List all files associated with specific file descriptors.

# lsof -d 2

This lists all files that have been opened as file descriptor `2`

.

You may also specify ranges of file descriptors:

# lsof -d 0-2

This would list all files with file descriptors 0, 1 and 2.

There are also many special values, such as `mem`

, that lists memory-mapped files:

# lsof -d mem

Or `txt`

for programs loaded in memory and executing:

# lsof -d txt

## Output PIDs of processes using some resource.

# lsof -t -i

The `-t`

option outputs only PIDs of processes. Used together with `-i`

it outputs PIDs of all processes with network connections. It's easy to kill all processes that use network:

# kill -9 `lsof -t -i`

## Repeat listing files.

# lsof -r 1

The `-r`

option makes lsof repeatedly list files until interrupted. Argument `1`

means repeat the listing every 1 second. This option is best combined with a narrower query such as monitoring user network file activity:

# lsof -r 1 -u john -i -a

## How to install lsof?

Lsof comes preinstalled on many Unix systems. If your system doesn't have it, try to install it from the source.

BSD supplies its own utility that does similar things, it's called **fstat**.

For the full documentation of lsof see the man lsof page or type `lsof -h`

for a small cheat sheet.

Have fun with lsof!

**7**Comments December 16, 2009

# MIT Linear Algebra, Lecture 3: Matrix Multiplication and Inverse Matrices

This is the third post in an article series about MIT's course "Linear Algebra". In this post I will review lecture three on five ways to **multiply matrices**, **inverse matrices** and an algorithm for finding inverse matrices called **Gauss-Jordan elimination**.

The first lecture covered the geometry of linear equations and the second lecture covered the matrix elimination.

Here is lecture three.

## Lecture 3: Matrix Multiplication and Inverse Matrices

Lecture three starts with **five ways to multiply matrices**.

The first way is the classical way. Suppose we are given a matrix **A** of size mxn with elements a_{ij} and a matrix **B** of size nxp with elements b_{jk}, and we want to find the product **A**·**B**. Multiplying matrices **A** and **B** will produce matrix **C** of size mxp with elements .

Here is how this sum works. To find the first element c_{11} of matrix **C**, we sum over the 1st row of **A** and the 1st column of **B**. The sum expands to c_{11} = a_{11}·b_{11} + a_{12}·b_{21} + a_{13}·b_{31} + ... + a_{1n}·b_{n1}. Here is a visualization of the summation:

We continue this way until we find all the elements of matrix **C**. Here is another visualization of finding c_{23}:

The second way is to take each column in **B**, multiply it by the whole matrix **A** and put the resulting column in the matrix **C**. The columns of **C** are combinations of columns of **A**. (Remember from previous lecture that a matrix times a column is a column.)

For example, to get column 1 of matrix **C**, we multiply **A**·(column 1 of matrix **B**):

The third way is to take each row in **A**, multiply it by the whole matrix **B** and put the resulting row in the matrix **C**. The rows of **C** are combinations of rows of **B**. (Again, remember from previous lecture that a row times a matrix is a row.)

For example, to get row 1 of matrix **C**, we multiply row 1 of matrix **A** with the whole matrix **B**:

The fourth way is to look at the product of **A**·**B** as a sum of (columns of **A**) times (rows of **B**).

Here is an example:

The fifth way is to chop matrices in blocks and multiply blocks by any of the previous methods.

Here is an example. Matrix **A** gets subdivided in four submatrices A_{1} A_{2} A_{3} A_{4}, matrix **B** gets divided in four submatrices B_{1} B_{2} B_{3} B_{4} and the blocks get treated like simple matrix elements.

Here is the visualization:

Element **C**_{1}, for example, is obtained by multiplying **A**_{1}·**B**_{1} + **A**_{2}·**B**_{3}.

Next the lecture proceeds to finding the **inverse matrices**. An inverse of a matrix **A** is another matrix, such that **A ^{-1}**·

**A**=

**I**, where I is the identity matrix. In fact if

**A**is the inverse matrix of a square matrix

^{-1}**A**, then it's both the left-inverse and the right inverse, i.e.,

**A**·

^{-1}**A**=

**A**·

**A**=

^{-1}**I**.

If a matrix **A** has an inverse then it is said to be **invertible** or **non-singular**.

Matrix A is singular if we can find a non-zero vector **x** such that A·**x** = **0**. The proof is easy. Suppose A is not singular, i.e., there exists matrix A^{-1}. Then A^{-1}·A·**x** = **0**·A^{-1}, which leads to a false statement that **x** = **0**. Therefore A must be singular.

Another way of saying that matrix **A** is singular is to say that columns of matrix **A** are linearly dependent (one ore more columns can be expressed as a linear combination of others).

Finally, the lecture shows a deterministic method for finding the inverse matrix. This method is called the **Gauss-Jordan elimination**. In short, Gauss-Jordan elimination transforms augmented matrix (**A**|**I**) into (**I**|**A**^{-1}) by using only row eliminations.

Please watch the lecture to find out how it works in all the details:

Direct link: http://www.youtube.com/watch?v=FX4C-JpTFgY

Topics covered in lecture three:

- [00:51] The first way to multiply matrices.
- [04:50] When are we allowed to multiply matrices?
- [06:45] The second way to multiply matrices.
- [10:10] The third way to multiply matrices.
- [12:30] What is the result of multiplying a column of A and a row of B?
- [15:30] The fourth way to multiply matrices.
- [18:35] The fifth way to multiply matrices by blocks.
- [21:30] Inverses for square matrices.
- [24:55] Singular matrices (no inverse matrix exists).
- [30:00] Why singular matrices can't have inverse?
- [36:20] Gauss-Jordan elimination.
- [41:20] Gauss-Jordan idea A·I -> I·A
^{-1}.

Here are my notes of lecture three:

Have fun with this lecture! The next post is going to be about the A=LU matrix decomposition (also known as factorization).

PS. This course is taught from Introduction to Linear Algebra textbook. Get it here: