> For the complete documentation index, see [llms.txt](https://julienbeaulieu.gitbook.io/wiki/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://julienbeaulieu.gitbook.io/wiki/sciences/math/linear-algebra/operations/matrix-multiplication.md). # Matrix Multiplication ### Matrix Multiplication The product of two matrices is defined *only* when the number of columns of the first matrix is the same as the number of rows of the second; in other words, it is only possible to multiply m x n and n x p size matrices. The reason for this becomes clear upon defining the product: ![](https://846345873-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LagOeJ2nL90MQERwhxy%2F-LeYY4QtuY_3sZTsfqYF%2F-LeYoFQeCxEZRutA0drm%2Fimage.png?alt=media\&token=848f4f3d-237f-4683-bfbf-5e92bff41aa6) ![](https://846345873-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LagOeJ2nL90MQERwhxy%2F-LeYY4QtuY_3sZTsfqYF%2F-LeYoZE7EU3IKJp_yu3Q%2Fimage.png?alt=media\&token=8e4832e8-60fa-4eae-8792-4a799499b2b3) ![](https://846345873-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LagOeJ2nL90MQERwhxy%2F-LeYY4QtuY_3sZTsfqYF%2F-LeYohmJIFQJ3yQmWU_9%2Fimage.png?alt=media\&token=726b8cb1-f22b-4f99-8249-eac9a4c8f68d) Another way to see is this: ![](https://846345873-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LagOeJ2nL90MQERwhxy%2F-Les_bNJt4mr4K_-rEub%2F-Lese3MiJ_QE8RNvt3Jl%2Fimage.png?alt=media\&token=5aab9bd5-10a2-4c97-bc42-3bbe0d106db6) and ![](https://846345873-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LagOeJ2nL90MQERwhxy%2F-Les_bNJt4mr4K_-rEub%2F-LeseBXMNMvZAvO3pzXp%2Fimage.png?alt=media\&token=c183b2af-ffb6-4ee9-a0e4-cabab4ca6618) Another way to look at multiplication through columns ![](https://846345873-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LagOeJ2nL90MQERwhxy%2F-Les_bNJt4mr4K_-rEub%2F-LesoAgY4a774qoqxhrD%2Fimage.png?alt=media\&token=445d2724-077c-4a16-aa25-94a30e8fa48f) 4th way to multiply ![](https://846345873-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LagOeJ2nL90MQERwhxy%2F-Les_bNJt4mr4K_-rEub%2F-LespXeX7f8xQN3m-aOX%2Fimage.png?alt=media\&token=e31331c3-58d5-4f12-9220-e9fb1095764a) Also, the **multiplication of matrices need not be commutative**. Therefore AB =/= BA generally. When AB = BA then AB are said to commute. This is the case of the identity matrix. ### Elimination Say you have this matrix you want to solve: ![](https://846345873-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LagOeJ2nL90MQERwhxy%2F-Les_bNJt4mr4K_-rEub%2F-LevgpAxcKtEHm7M51_5%2Fimage.png?alt=media\&token=d65556f3-b28f-4832-8870-5dfbf22220d3) Find the matrix you need to multiply it by to solve it. Or to get U (upper triangle which allows you to easily solve the system. Step 1 : You want a 0 in position (2, 1) and (3,1) - but in this example there is already a 0 in (3,1). ![](https://846345873-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LagOeJ2nL90MQERwhxy%2F-Les_bNJt4mr4K_-rEub%2F-Levgf0R-K7sWgIzgEz9%2Fimage.png?alt=media\&token=1f3dbdf3-25df-4fa8-92d9-7888a7be8248) Step 2: You want a 0 in position (3,2). So in this example you subtract 2 x row 2 from row 3 to get the 0. ![](https://846345873-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LagOeJ2nL90MQERwhxy%2F-Les_bNJt4mr4K_-rEub%2F-LeshfEOdQgueXa3Uh5H%2Fimage.png?alt=media\&token=6272463b-d492-49e5-ab35-0c7a3e1ca880) So now, z=5, and you can easily solve the rest. You can change the order in which you do multiplications with matrix multiplication. ![](https://846345873-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LagOeJ2nL90MQERwhxy%2F-Les_bNJt4mr4K_-rEub%2F-LesibEtxs5HNa3-i9kr%2Fimage.png?alt=media\&token=a12a1e6d-f38f-4470-a2ae-44da9f80f5b7) Let's finish the topic of elimination.‌ Ex: 2 x 2 elimnation. Let A be a matrix as below where I can do elimination, but no pivots. I want to get from A to U to solve A. But then I want to know how is A related to U where there is a matrix L where A = LU. How do you get there?‌ First, to solve A and get U (that is then easy to solve), I multiply by my elementary matrix at the position 2, 1 (E(2,1)) because that is how I get a 0 in position 2,1. Therefore we get:​‌ ![](blob:https://app.gitbook.com/7052d423-ab6d-4f74-b352-2810fe93919b) Then to get A = L U: you need to multiply E, (2,1) by the inverse which becomes L (-4 becomes 4).​‌ ![](blob:https://app.gitbook.com/65ca6b0f-36f5-4124-a81a-1508453df632) Where L is the Lower triangle, and U is the Upper triangle.
Now let's try to do this is a 3x3 matrix. What are the steps to producing elimination? ![](https://846345873-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LagOeJ2nL90MQERwhxy%2F-Les_bNJt4mr4K_-rEub%2F-LevkGMB4CUMdukH9FlO%2Fimage.png?alt=media\&token=8d24ed7a-5829-4826-b2d3-f9469278cedf) Now, suppose we want all the E's on the right hand side of the equation. We get: ![](https://846345873-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LagOeJ2nL90MQERwhxy%2F-Les_bNJt4mr4K_-rEub%2F-Levkcxa2uUZiJjkHdN5%2Fimage.png?alt=media\&token=d8c6b375-f680-4300-bdb4-ada8a8db07b9) So L is the product of inverses. Why do we do this? Because when you multiply the non inverses, you don't get a good matrix. The multipliers go directly into L (see the number 10 in the matrix below). However, when you multiply the inverses, you get a clean L with no 0 in position 3,1. See: ![](https://846345873-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LagOeJ2nL90MQERwhxy%2F-Les_bNJt4mr4K_-rEub%2F-LevmeVEJGXniYNwn0e1%2Fimage.png?alt=media\&token=06f957c3-8d48-4538-9362-8ba31be2d3c3) ### Cost of the operations Say you have a matrix nxn where n=100. How many operations will we have to do with elimination? Turns out that the operations for A and b (Ax = b) there will be: ![](https://846345873-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LagOeJ2nL90MQERwhxy%2F-Les_bNJt4mr4K_-rEub%2F-LevviSSk8gEPCa3e1IE%2Fimage.png?alt=media\&token=0273280e-bba0-4be4-b9ae-ce55947b44fa)