{"id":31692,"date":"2017-06-12T14:57:29","date_gmt":"2017-06-12T19:57:29","guid":{"rendered":"http:\/\/blogs.ams.org\/mathgradblog\/?p=31692"},"modified":"2017-06-19T16:52:34","modified_gmt":"2017-06-19T21:52:34","slug":"matrix-multiplication-human-way","status":"publish","type":"post","link":"https:\/\/blogs.ams.org\/mathgradblog\/2017\/06\/12\/matrix-multiplication-human-way\/","title":{"rendered":"Matrix Multiplication, the human way!"},"content":{"rendered":"

Having to do copious calculations by hand when preparing for an exam, I came to realize that there was an alternative way of interpreting a matrix multiplication. This new insight would allow me to instantly guess the following product without ever doing any numerical multiplication<\/em>:
\n\\[\\begin{bmatrix}
\n1 & 2 & 3 \\\\
\n4 & 5 & 6 \\\\
\n7 & -8 & 0
\n\\end{bmatrix}
\n\\begin{bmatrix}
\n0 & 0 & 0 \\\\
\n0& 1 & 0 \\\\
\n1& 0 & 0
\n\\end{bmatrix}
\n=
\n\\begin{bmatrix}
\n3 & 2 & 0 \\\\
\n6 & 5 & 0 \\\\
\n0 & -8 & 0
\n\\end{bmatrix}\\]<\/p>\n

Was there a way to have known that the first column of the product would be the third column of the first matrix?<\/p>\n

<\/p>\n

MATRIX TIMES VECTOR<\/strong><\/p>\n

Observation:<\/strong> If \"A\" has $n$ columns and $v$ is an \"n\"-vector, then<\/p>\n

\\[Av=\\begin{bmatrix}
\nc & c & c & \\cdots \\\\
\no & o & o & \\cdots \\\\
\nl & l & l & \\cdots \\\\
\nu & u & u & \\cdots \\\\
\nm & m & m & \\cdots \\\\
\nn & n & n & \\cdots \\\\
\n\\end{bmatrix}
\n\\begin{bmatrix}
\na\u00a0 \\\\
\nb \\\\
\nc \\\\
\n\\vdots
\n\\end{bmatrix}
\n=
\na* \\begin{bmatrix}
\n1^{st}\u00a0 \\\\
\nc \\\\
\no \\\\
\nl \\\\
\nu \\\\
\nm \\\\
\nn
\n\\end{bmatrix}
\n+b*\u00a0 \\begin{bmatrix}
\n2^{nd}\u00a0 \\\\
\nc \\\\
\no \\\\
\nl \\\\
\nu \\\\
\nm \\\\
\nn
\n\\end{bmatrix}
\n+c* \\begin{bmatrix}
\n3^{rd}\u00a0 \\\\
\nc \\\\
\no \\\\
\nl \\\\
\nu \\\\
\nm \\\\
\nn
\n\\end{bmatrix}+ \\cdots \\]<\/p>\n

That is, the product is a linear combination of the columns with coefficients coming from the vector.<\/p>\n

Examples:<\/p>\n

1.<\/p>\n

\\[\\begin{bmatrix}
\n1 & -5 & 3 \\\\
\n0 & 0.5 & 2\\\\
\n1 & -8 & 0
\n\\end{bmatrix}
\n\\begin{bmatrix}
\n2\\\\
\n-1 \\\\
\n0
\n\\end{bmatrix}
\n= 2* \\begin{bmatrix} 1st\\\\ col \\end{bmatrix} + (-1)*\\begin{bmatrix} 2nd\\\\ col \\end{bmatrix} + 0\u00a0\u00a0 \\\\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\\u00a0 \\ \\ \\ \\ \\ \\\u00a0 \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\ \\\u00a0 =
\n2 \\begin{bmatrix}
\n1 \\\\
\n0 \\\\
\n1
\n\\end{bmatrix} -\\begin{bmatrix}
\n-5 \\\\
\n0.5 \\\\
\n-8
\n\\end{bmatrix}+0 = \\begin{bmatrix}
\n7 \\\\
\n-0.5 \\\\
\n10
\n\\end{bmatrix}\\]<\/p>\n

2. What vector to multiply a matrix \"A\" into, so that we get the second column of \"A\" as the product?<\/p>\n

Answer: \\[ \\begin{bmatrix}
\n0 \\\\
\n1 \\\\
\n0 \\\\
\n\\vdots
\n\\end{bmatrix}. \\]<\/p>\n

It is not only the practical calculations that benefit from this new method. Some lemmas and theorems of linear algebra become more obvious and accessible. For example:<\/p>\n

Ax=0 has a nontrivial solution iff the columns of A are linearly dependent (as vectors).<\/p>\n

dimension of {Ax: x ranging over all column vectors} = number of independent columns of A<\/p>\n

Given \"A\" and \"b\", \"Av=b\" has a solution iff \"b\" can be written as a linear combination of columns of \"A\".<\/p>\n

 <\/p>\n

MATRIX TIMES MATRIX<\/strong><\/p>\n

In computing<\/p>\n

\\[AB=\\begin{bmatrix}
\nc & c & c & \\cdots \\\\
\no & o & o & \\cdots \\\\
\nl & l & l & \\cdots \\\\
\nu & u & u & \\cdots \\\\
\nm & m & m & \\cdots \\\\
\nn & n & n & \\cdots \\\\
\n\\end{bmatrix}
\n\\begin{bmatrix}
\nc & c & c & \\cdots \\\\
\no & o & o & \\cdots \\\\
\nl & l & l & \\cdots \\\\
\nu & u & u & \\cdots \\\\
\nm & m & m & \\cdots \\\\
\nn & n & n & \\cdots \\\\
\n\\end{bmatrix}
\n, \\ \\]<\/p>\n

To get the\u00a0 j’th\u00a0column of the product, ignore all other columns of B except the\u00a0 j\u2019th, and then do A*[column j of B], using the above method. Do this for all columns and you will have the product \"AB\".<\/p>\n

Examples:<\/p>\n

1.<\/p>\n

\\[\\begin{bmatrix}
\n1 & 2 & 3 \\\\
\n4 & 5 & -2 \\\\
\n7 & -4 & 0
\n\\end{bmatrix}
\n\\begin{bmatrix}
\n1 & 0 & 1 \\\\
\n0& 1 & 1 \\\\
\n2& 3 & 0
\n\\end{bmatrix} \\]<\/p>\n

The first<\/span> <\/strong>column will be<\/p>\n

\\[ \\begin{bmatrix}
\n1 & 2 & 3 \\\\
\n4 & 5 & -2 \\\\
\n7 & -4 & 0
\n\\end{bmatrix}
\n\\begin{bmatrix}
\n1\u00a0 \\\\
\n0 \\\\
\n2
\n\\end{bmatrix} =
\n1*\\begin{bmatrix}
\n1\u00a0 \\\\
\n4 \\\\
\n7
\n\\end{bmatrix} + 2* \\begin{bmatrix}
\n3\u00a0 \\\\
\n-2 \\\\
\n0
\n\\end{bmatrix} = \\begin{bmatrix}
\n7\\\\
\n0 \\\\
\n7
\n\\end{bmatrix} \\]<\/p>\n

The second<\/strong><\/span> column will be<\/p>\n

\\[ \\begin{bmatrix}
\n1 & 2 & 3 \\\\
\n4 & 5 & -2 \\\\
\n7 & -4 & 0
\n\\end{bmatrix}
\n\\begin{bmatrix}
\n0\u00a0 \\\\
\n1 \\\\
\n3
\n\\end{bmatrix} =
\n1*\\begin{bmatrix}
\n2\u00a0 \\\\
\n5 \\\\
\n-4
\n\\end{bmatrix} + 3* \\begin{bmatrix}
\n3\u00a0 \\\\
\n-2 \\\\
\n0
\n\\end{bmatrix} = \\begin{bmatrix}
\n11 \\\\
\n-1 \\\\
\n-4
\n\\end{bmatrix} \\]<\/p>\n

Column 3 is computed similarly, and the full result is:<\/p>\n

\\[\\begin{bmatrix}
\n1 & 2 & 3 \\\\
\n4 & 5 & -2 \\\\
\n7 & -4 & 0
\n\\end{bmatrix}
\n\\begin{bmatrix}
\n1 & 0 & 1 \\\\
\n0& 1 & 1 \\\\
\n2& 3 & 0
\n\\end{bmatrix} = \\begin{bmatrix}
\n7 & 11\u00a0 & 3 \\\\
\n0 & -1 & 9 \\\\
\n7 & -4 & 3
\n\\end{bmatrix} \\]<\/p>\n

Note: Most of the calculations above are doable in mind, and I have written them out to explain the procedure only.<\/p>\n

2. Multiply\u00a0 \\[A= \\begin{bmatrix}
\n2 & 33\u00a0 & 0 \\\\
\n0 & -1 & 9 \\\\
\n4\u00a0 & -14 & 13
\n\\end{bmatrix} \\]\u00a0 into a matrix \"B\" so that the columns 2 and 3 of A are interchanged.<\/p>\n

Answer:\u00a0 \\[ B=\\begin{bmatrix}
\n1 & 0 &\u00a0 0 \\\\
\n0 & 0 & 1 \\\\
\n0 & 1 &\u00a0\u00a0 0
\n\\end{bmatrix} \\]<\/p>\n

3. Find the 3rd column of the product<\/p>\n

\\[\\begin{bmatrix}
\n10 & 2 & 3 \\\\
\n4 & 0 & -2 \\\\
\n7 & -4 & 0
\n\\end{bmatrix}
\n\\begin{bmatrix}
\n1 & 0 & 1 \\\\
\n0& 1 & 1 \\\\
\n-2& 0 & -1
\n\\end{bmatrix} \\]<\/p>\n

Answer:<\/p>\n

thrid column of AB = A * third column of B. So<\/p>\n

\\[ \\begin{bmatrix}
\n10 & 2 & 3 \\\\
\n4 & 0 & -2 \\\\
\n7 & -4 & 0
\n\\end{bmatrix}
\n\\begin{bmatrix} 1 \\\\ 1 \\\\ -1 \\end{bmatrix}= \\begin{bmatrix} 9 \\\\ 6 \\\\ 3 \\end{bmatrix} \\]<\/p>\n

(Please verify!)<\/p>\n

 <\/p>\n

4. Is the following true or false? “If we change arrays in the second column of B, then in the product AB only the arrays in the second column may change — all other arrays on other columns will remain the same.”<\/em><\/p>\n

Answer: True.<\/p>\n

 <\/p>\n

Whether you are convinced that computing AB one column at a time is more practical than the conventional array-by-array multiplication or not, one cannot ignore its usefulness in helping one to “see” the linear algebra behind matrices and their multiplication. So, next time you encounter a sparse matrix save yourself tens of multiplications by zero!<\/p>\n

HOMEWORK<\/strong><\/p>\n

Can you guess and prove a row-wise version of the above?<\/p>\n

 <\/p>\n

<\/div>","protected":false},"excerpt":{"rendered":"

Having to do copious calculations by hand when preparing for an exam, I came to realize that there was an alternative way of interpreting a matrix multiplication. This new insight would allow me to instantly guess the following product without … Continue reading →<\/span><\/a><\/p>\n

<\/div>\n","protected":false},"author":118,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[12],"tags":[67,300,301],"class_list":["post-31692","post","type-post","status-publish","format-standard","hentry","category-math","tag-mathematics","tag-matrix-multiplication","tag-tips-and-tricks"],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p3gbww-8fa","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/posts\/31692","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/users\/118"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/comments?post=31692"}],"version-history":[{"count":26,"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/posts\/31692\/revisions"}],"predecessor-version":[{"id":31725,"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/posts\/31692\/revisions\/31725"}],"wp:attachment":[{"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/media?parent=31692"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/categories?post=31692"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/tags?post=31692"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}