definition of matrix representations

If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

To log in and use all the features of Khan Academy, please enable JavaScript in your browser.

Precalculus

Course: precalculus   >   unit 7, intro to matrices, matrix dimensions.

B = [ − 8 − 4 23 12 18 10 ] ‍  

Check your understanding

• Your answer should be
• an integer, like 6 ‍  
• a simplified proper fraction, like 3 / 5 ‍  
• a simplified improper fraction, like 7 / 4 ‍  
• a mixed number, like 1   3 / 4 ‍  
• an exact decimal, like 0.75 ‍  
• a multiple of pi, like 12   pi ‍   or 2 / 3   pi ‍  

Matrix elements

• (Choice A)   [ 1 2 6 4 5 − 2 ] ‍   A [ 1 2 6 4 5 − 2 ] ‍  
• (Choice B)   [ − 9 6 7 − 3 − 3 5 ] ‍   B [ − 9 6 7 − 3 − 3 5 ] ‍  
• (Choice C)   [ 2 6 8 7 − 3 1 ] ‍   C [ 2 6 8 7 − 3 1 ] ‍  
• (Choice D)   [ 2 10 8 6 − 3 1 ] ‍   D [ 2 10 8 6 − 3 1 ] ‍  

Want to join the conversation?

• Upvote Button navigates to signup page
• Downvote Button navigates to signup page
• Flag Button navigates to signup page

You are about to erase your work on this activity. Are you sure you want to do this?

Updated Version Available

There is an updated version of this activity. If you update to the most recent version of this activity, then your current progress on this activity will be erased. Regardless, your record of completion will remain. How would you like to proceed?

Mathematical Expression Editor

A linear transformation can be represented in terms of multiplication by a matrix.

We see now that the same type of representation applies for arbitrary vector spaces once a basis has been fixed for both the domain and target. In other words, given

A Geometrical Understanding of Matrices

My college course on linear algebra focused on systems of linear equations. i present a geometrical understanding of matrices as linear transformations, which has helped me visualize and relate concepts from the field..

24 October 2018

Beyond systems of equations

I took linear algebra in college, but the main thing I remember from the course was solving systems of linear equations by converting matrices to row echelon form. I did well in the class, but I had little intuition for matrices as geometric objects and almost none of the material stuck. In graduate school, I have discovered that having such a geometrical intuition for matrices—and for linear algebra more broadly—makes many concepts easier to understand, chunk, and remember.

For example, computing the determinant of a matrix is tedious. But if we think of the determinant of a matrix as the signed scale factor representing how much a matrix transforms the volume of an n n n -cube into an m m m -dimensional parallelepiped, it is straightforward to see why a matrix with a determinant of 0 0 0 is singular. It is because the matrix is collapsing space along at least one dimension.

The goal of this post is to lay the ground work for understanding matrices as geometric objects. I focus on matrices because they effect how I think of vectors, vector spaces, the determinant, null spaces, spans, ranks, inverse matrices, singular values, and so on. In my mind, every one of these concepts is easier to understand with a strong, geometrical understanding of matrices. For simplicity, I will focus on real-valued matrices and vectors, and I error on the side of intuitive examples rather than generalizations.

Matrices as linear transformations

In linear algebra, we are interested in equations of the following form:

b = A x \textbf{b} = A \textbf{x} b = A x

Where b ∈ R m \textbf{b} \in \mathbb{R}^{m} b ∈ R m , A ∈ R m × n A \in \mathbb{R}^{m \times n} A ∈ R m × n , and x ∈ R n \textbf{x} \in \mathbb{R}^{n} x ∈ R n . One way to think about this equation is that A A A represents a system of m m m linear equations, each with n n n variables, and x \textbf{x} x represents a solution to this system. But there is another way to think of the matrix A A A , which is as a linear function f f f from R n \mathbb{R}^n R n to R m \mathbb{R}^m R m :

f ( x ) = A x f(\textbf{x}) = A \textbf{x} f ( x ) = A x

In my mind, the easiest way to see how matrices are linear transformations is to observe that the columns of a matrix A A A represent where the standard basis vectors in R n \mathbb{R}^n R n map to in R m \mathbb{R}^m R m . Let’s look at an example. Recall that the standard basis vectors in R 3 \mathbb{R}^3 R 3 are:

e 1 = [ 1 0 0 ] e 2 = [ 0 1 0 ] e 3 = [ 0 0 1 ] \textbf{e}_1 = \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} \qquad \textbf{e}_2 = \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix} \qquad \textbf{e}_3 = \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix} e 1 ​ = ⎣ ⎢ ⎡ ​ 1 0 0 ​ ⎦ ⎥ ⎤ ​ e 2 ​ = ⎣ ⎢ ⎡ ​ 0 1 0 ​ ⎦ ⎥ ⎤ ​ e 3 ​ = ⎣ ⎢ ⎡ ​ 0 0 1 ​ ⎦ ⎥ ⎤ ​

By definition, this means that every vector in R 3 \mathbb{R}^3 R 3 is a linear combination of this set of basis vectors:

x = [ x 1 x 2 x 3 ] = x 1 [ 1 0 0 ] + x 2 [ 0 1 0 ] + x 3 [ 0 0 1 ] \textbf{x} = \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = x_1 \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} + x_2 \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix} + x_3 \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix} x = ⎣ ⎢ ⎡ ​ x 1 ​ x 2 ​ x 3 ​ ​ ⎦ ⎥ ⎤ ​ = x 1 ​ ⎣ ⎢ ⎡ ​ 1 0 0 ​ ⎦ ⎥ ⎤ ​ + x 2 ​ ⎣ ⎢ ⎡ ​ 0 1 0 ​ ⎦ ⎥ ⎤ ​ + x 3 ​ ⎣ ⎢ ⎡ ​ 0 0 1 ​ ⎦ ⎥ ⎤ ​

Now let’s see what happens when we matrix multiply one of these standard basis vectors, say e 2 \textbf{e}_2 e 2 ​ , by a transformation matrix A A A :

[ 0 0 0 ] [ 1 2 0 − 5 3 1 ] ⏞ A [ 0 0 0 ] [ 0 1 0 ] ⏞ e 2 = [ 0 + 2 + 0 0 + 3 + 0 ] = [ 2 3 ] \overbrace{ \vphantom{\begin{bmatrix}0\\0\\0\end{bmatrix}} \left[\begin{array}{c|c|c} 1 & \textcolor{#bc2612}{2} & 0 \\ -5 & \textcolor{#bc2612}{3} & 1 \end{array}\right] }^{A} \overbrace{ \vphantom{\begin{bmatrix}0\\0\\0\end{bmatrix}} \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix} }^{\textbf{e}_2} = \begin{bmatrix} 0 + \textcolor{#bc2612}{2} + 0 \\ 0 + \textcolor{#bc2612}{3} + 0 \end{bmatrix} = \begin{bmatrix} \textcolor{#bc2612}{2} \\ \textcolor{#bc2612}{3} \end{bmatrix} ⎣ ⎢ ⎡ ​ 0 0 0 ​ ⎦ ⎥ ⎤ ​ [ 1 − 5 ​ 2 3 ​ 0 1 ​ ] ​ A ​ ⎣ ⎢ ⎡ ​ 0 0 0 ​ ⎦ ⎥ ⎤ ​ ⎣ ⎢ ⎡ ​ 0 1 0 ​ ⎦ ⎥ ⎤ ​ ​ e 2 ​ ​ = [ 0 + 2 + 0 0 + 3 + 0 ​ ] = [ 2 3 ​ ]

In words, the second column of A A A tells us where the second basis vector in R 3 \mathbb{R}^3 R 3 maps to in R 2 \mathbb{R}^2 R 2 . If we horizontally stack the standard basis vectors into a 3 × 3 3 \times 3 3 × 3 matrix, we can see where each basis vector maps to in R 2 \mathbb{R}^2 R 2 with a single matrix multiplication:

[ 1 2 0 − 5 3 1 ] [ 1 0 0 0 1 0 0 0 1 ] = [ 1 2 0 − 5 3 1 ] \left[\begin{array}{c|c|c} 1 & 2 & 0 \\ -5 & 3 & 1 \end{array}\right] \left[\begin{array}{c|c|c} \textcolor{#11accd}{1} & \textcolor{#bc2612}{0} & \textcolor{#807504}{0} \\ \textcolor{#11accd}{0} & \textcolor{#bc2612}{1} & \textcolor{#807504}{0} \\ \textcolor{#11accd}{0} & \textcolor{#bc2612}{0} & \textcolor{#807504}{1} \end{array}\right] = \left[\begin{array}{c|c|c} \textcolor{#11accd}{1} & \textcolor{#bc2612}{2} & \textcolor{#807504}{0} \\ \textcolor{#11accd}{-5} & \textcolor{#bc2612}{3} & \textcolor{#807504}{1} \end{array}\right] [ 1 − 5 ​ 2 3 ​ 0 1 ​ ] ⎣ ⎢ ⎡ ​ 1 0 0 ​ 0 1 0 ​ 0 0 1 ​ ⎦ ⎥ ⎤ ​ = [ 1 − 5 ​ 2 3 ​ 0 1 ​ ]

Now here’s the cool thing. We can express any transformed 2 2 2 -vector as a linear combination of f ( e 1 ) f(\textbf{e}_1) f ( e 1 ​ ) , f ( e 2 ) f(\textbf{e}_2) f ( e 2 ​ ) , and f ( e 3 ) f(\textbf{e}_3) f ( e 3 ​ ) , where the coefficients are the components of the untransformed 3 3 3 -vector. For example, if x = [ 1.2 1.5 − 2 ] ⊤ \textbf{x} = \begin{bmatrix} 1.2 & 1.5 & -2 \end{bmatrix}^{\top} x = [ 1 . 2 ​ 1 . 5 ​ − 2 ​ ] ⊤ , then:

[ 0 0 0 ] [ 1 2 0 − 5 3 1 ] ⏞ A [ 0 0 0 ] [ 1.2 1.5 − 2 ] ⏞ x = [ 0 0 0 ] [ 4.2 − 3.5 ] ⏞ f ( x ) (1) \overbrace{ \vphantom{\begin{bmatrix}0\\0\\0\end{bmatrix}} \left[\begin{array}{c|c|c} 1 & 2 & 0 \\ -5 & 3 & 1 \end{array}\right]}^{A} \overbrace{ \vphantom{\begin{bmatrix}0\\0\\0\end{bmatrix}} \begin{bmatrix} 1.2 \\ 1.5 \\ -2 \end{bmatrix}}^{\textbf{x}} = \overbrace{ \vphantom{\begin{bmatrix}0\\0\\0\end{bmatrix}} \begin{bmatrix} 4.2 \\ -3.5 \end{bmatrix}}^{f(\textbf{x})} \tag{1} ⎣ ⎢ ⎡ ​ 0 0 0 ​ ⎦ ⎥ ⎤ ​ [ 1 − 5 ​ 2 3 ​ 0 1 ​ ] ​ A ​ ⎣ ⎢ ⎡ ​ 0 0 0 ​ ⎦ ⎥ ⎤ ​ ⎣ ⎢ ⎡ ​ 1 . 2 1 . 5 − 2 ​ ⎦ ⎥ ⎤ ​ ​ x ​ = ⎣ ⎢ ⎡ ​ 0 0 0 ​ ⎦ ⎥ ⎤ ​ [ 4 . 2 − 3 . 5 ​ ] ​ f ( x ) ​ ( 1 )

1.2 [ 1 − 5 ] ⏞ f ( e 1 ) + 1.5 [ 2 3 ] ⏞ f ( e 2 ) − 2 [ 0 1 ] ⏞ f ( e 3 ) = [ 1.2 + 3 + 0 − 6 + 4.5 − 2 ] = [ 4.2 − 3.5 ] ⏞ f ( x ) (2) 1.2 \overbrace{\begin{bmatrix} 1 \\ -5 \end{bmatrix}}^{f(\textbf{e}_1)} + 1.5 \overbrace{\begin{bmatrix} 2 \\ 3 \end{bmatrix}}^{f(\textbf{e}_2)} - 2 \overbrace{\begin{bmatrix} 0 \\ 1 \end{bmatrix}}^{f(\textbf{e}_3)} = \begin{bmatrix} 1.2 + 3 + 0 \\ -6 + 4.5 - 2 \end{bmatrix} = \overbrace{\begin{bmatrix} 4.2 \\ -3.5 \end{bmatrix}}^{f(\textbf{x})} \tag{2} 1 . 2 [ 1 − 5 ​ ] ​ f ( e 1 ​ ) ​ + 1 . 5 [ 2 3 ​ ] ​ f ( e 2 ​ ) ​ − 2 [ 0 1 ​ ] ​ f ( e 3 ​ ) ​ = [ 1 . 2 + 3 + 0 − 6 + 4 . 5 − 2 ​ ] = [ 4 . 2 − 3 . 5 ​ ] ​ f ( x ) ​ ( 2 )

It’s worth staring at these equations for a few minutes. In my mind, seeing Equations 1 1 1 and 2 2 2 together helped me understand why matrix multiplication is defined as it is. When we perform matrix multiplication, we are projecting a vector or vectors into a new space defined by the columns of the transformation matrix. And f ( x ) f(\textbf{x}) f ( x ) is just a linear combination of the columns of A A A , where the coefficients are the components of x \textbf{x} x .

In my mind, changing how we see the equation b = A x \textbf{b} = A \textbf{x} b = A x is not trivial. In the textbook Numerical Linear Algebra (Trefethen & Bau III, 1997) , the authors claim that seeing matrices this way is “essential for a proper understanding of the algorithms of numerical linear algebra.”

This linearity is what allows us to say concretely that any linear transformation, f : R n → R m f: \mathbb{R}^n \rightarrow \mathbb{R}^m f : R n → R m , can be represented as a linear combination of the transformed basis vectors of x \textbf{x} x , which can be encoded as a matrix-vector multiplication:

x = x 1 e 1 + x 2 e 2 + ⋯ + x n e n f ( x ) = f ( x 1 e 1 + x 2 e 2 + ⋯ + x n e n ) = f ( x 1 e 1 ) + f ( x 2 e 2 ) + ⋯ + f ( x n e n ) Additivity = x 1 f ( e 1 ) + x 2 f ( e 2 ) + ⋯ + x n f ( e n ) Homogeneity of degree  1 = [ f ( e 1 ) f ( e 2 ) … f ( e n ) ] x \begin{aligned} \textbf{x} &= x_1 \textbf{e}_1 + x_2 \textbf{e}_2 + \dots + x_n \textbf{e}_n \\ f(\textbf{x}) &= f(x_1 \textbf{e}_1 + x_2 \textbf{e}_2 + \dots + x_n \textbf{e}_n) \\ &= f(x_1 \textbf{e}_1) + f(x_2 \textbf{e}_2) + \dots + f(x_n \textbf{e}_n) && \text{Additivity} \\ &= x_1 f(\textbf{e}_1) + x_2 f(\textbf{e}_2) + \dots + x_n f(\textbf{e}_n) && \text{Homogeneity of degree $1$} \\ &= \left[\begin{array}{c|c|c|c} f(\textbf{e}_1) & f(\textbf{e}_2) & \dots & f(\textbf{e}_n) \end{array}\right] \textbf{x} \end{aligned} x f ( x ) ​ = x 1 ​ e 1 ​ + x 2 ​ e 2 ​ + ⋯ + x n ​ e n ​ = f ( x 1 ​ e 1 ​ + x 2 ​ e 2 ​ + ⋯ + x n ​ e n ​ ) = f ( x 1 ​ e 1 ​ ) + f ( x 2 ​ e 2 ​ ) + ⋯ + f ( x n ​ e n ​ ) = x 1 ​ f ( e 1 ​ ) + x 2 ​ f ( e 2 ​ ) + ⋯ + x n ​ f ( e n ​ ) = [ f ( e 1 ​ ) ​ f ( e 2 ​ ) ​ … ​ f ( e n ​ ) ​ ] x ​ ​ Additivity Homogeneity of degree 1 ​

See the Appendix for a proof of the linearity of matrix transformations.

Visualizing matrix transformations

The linearity of matrix transformations can be visualized beautifully. For ease of visualization, let’s only consider 2 × 2 2 \times 2 2 × 2 matrices, which represent linear transformations from R 2 \mathbb{R}^2 R 2 to R 2 \mathbb{R}^2 R 2 . For example, consider the following matrix transformation A A A of a vector x = [ 1 2 ] ⊤ \textbf{x} = \begin{bmatrix} 1 & 2 \end{bmatrix}^{\top} x = [ 1 ​ 2 ​ ] ⊤ :

[ 2 − 1 0 1 ] ⏞ A [ 1 2 ] ⏞ x = [ 0 2 ] ⏞ f ( x ) \overbrace{\left[\begin{array}{c|c|c} \textcolor{#11accd}{2} & \textcolor{#bc2612}{-1} \\ \textcolor{#11accd}{0} & \textcolor{#bc2612}{1} \end{array}\right]}^{A} \overbrace{\begin{bmatrix} 1 \\ 2 \end{bmatrix}}^{\textbf{x}} = \overbrace{\begin{bmatrix} 0 \\ 2 \end{bmatrix}}^{f(\textbf{x})} [ 2 0 ​ − 1 1 ​ ] ​ A ​ [ 1 2 ​ ] ​ x ​ = [ 0 2 ​ ] ​ f ( x ) ​

We can visualize two important properties of this operation (Figure 1 1 1 ). First, the columns of A A A represent where the standard basis vectors in R 2 \mathbb{R}^2 R 2 land in this transformed vector space.

Second, in the new vector space, the vector f ( x ) f(\textbf{x}) f ( x ) is a linear combination of these transformed vectors. This is particularly useful to visualize by coloring unit squares and seeing how they are transformed. You can imagine that not just a vector is transformed by a matrix but that all of R n \mathbb{R}^n R n is transformed an m × n m \times n m × n matrix. Note that the determinant of the matrix is also visualized here. It is 2 2 2 .

Types of linear transformations

Now that we have some intuition for how matrix transformations represent linear functions, we might want to ask: what kind of transformations can we perform with matrices? A consequence of the linearity of matrix transformations is that we can only modify a vector space in particular ways such as by rotating, reflecting, scaling, shearing, and projecting. Intuitively, the hallmark of a linear transformation is that evenly spaced points before the transformation are evenly spaced after the transformation (Figure 2 a 2\text{a} 2 a ).

This makes sense. Linear functions are polynomials of degree one or less, meaning variables change at fixed rates. Conversely, what we cannot represent with a linear transformation is anything that would deform the space in such a way that evenly spaced points in R n \mathbb{R}^n R n are unevenly spaced in R m \mathbb{R}^m R m (Figure 2 b 2\text{b} 2 b ).

Now let’s look at some specific types of matrix transformations. To keep things simple, we’ll only consider square n × n n \times n n × n matrices. This is by no means an exhaustive or formal look at every type of matrix. The idea is to see how our geometrical understanding so far relates to familiar types of matrices.

Diagonal matrices

In my opinion, a diagonal matrix is the easiest matrix to understand once you understand that the columns of a matrix A A A represent where the standard basis vectors map to in a new vector space defined by A A A . For example, consider an arbitrary n × n n \times n n × n diagonal matrix with scalar values α 1 , α 2 , … , α n \alpha_1, \alpha_2, \dots, \alpha_n α 1 ​ , α 2 ​ , … , α n ​ along its diagonal. If we think of the columns of the matrix as defining a new vector subspace, it is clear that each component in a transformed vector x \textbf{x} x is only modified by one value on the diagonal:

[ α 1 ⋱ α i ⋱ α n ] [ x 1 ⋮ x i ⋮ x n ] = x 1 [ α 1 ⋮ ⋮ ⋮ ⋮ ] + ⋯ + x i [ ⋮ ⋮ α i ⋮ ⋮ ] + ⋯ + x n [ ⋮ ⋮ ⋮ ⋮ α n ] \begin{bmatrix} \textcolor{#11accd}{\alpha_1} & & & & \\ & \ddots & & & \\ & & \textcolor{#bc2612}{\alpha_i} & & \\ & & & \ddots & \\ & & & & \textcolor{#807504}{\alpha_n} \end{bmatrix} \begin{bmatrix} x_1 \\ \vdots \\ x_i \\ \vdots \\ x_n \end{bmatrix} = x_1 \begin{bmatrix} \textcolor{#11accd}{\alpha_1} \\ \phantom{\vdots} \\ \phantom{\vdots} \\ \phantom{\vdots} \\ \phantom{\vdots} \end{bmatrix} + \dots + x_i \begin{bmatrix} \phantom{\vdots} \\ \phantom{\vdots} \\ \textcolor{#bc2612}{\alpha_i} \\ \phantom{\vdots} \\ \phantom{\vdots} \end{bmatrix} + \dots + x_n \begin{bmatrix} \phantom{\vdots} \\ \phantom{\vdots} \\ \phantom{\vdots} \\ \phantom{\vdots} \\ \textcolor{#807504}{\alpha_n} \end{bmatrix} ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ ​ α 1 ​ ​ ⋱ ​ α i ​ ​ ⋱ ​ α n ​ ​ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ ​ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ ​ x 1 ​ ⋮ x i ​ ⋮ x n ​ ​ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ ​ = x 1 ​ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ ​ α 1 ​ ⋮ ⋮ ⋮ ⋮ ​ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ ​ + ⋯ + x i ​ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ ​ ⋮ ⋮ α i ​ ⋮ ⋮ ​ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ ​ + ⋯ + x n ​ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ ​ ⋮ ⋮ ⋮ ⋮ α n ​ ​ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ ​

This means a diagonal matrix is constrained in how it can modify a set of vectors (Figure 3 3 3 ). For example, it can stretch the i i i -th component of a vector with α i > 1 \alpha_i > 1 α i ​ > 1 , or it can reflect the i i i -th component with α i < 0 \alpha_i < 0 α i ​ < 0 . You cannot shear a vector subspace with a diagonal matrix.

Note that the identity matrix is a diagonal matrix where ∀ i , α i = 1 \forall i, \alpha_i = 1 ∀ i , α i ​ = 1 , meaning the standard basis vectors are not changed. It has a determinant of 1 1 1 because it does not modify a vector subspace.

Shear matrices

A shear matrix is so-named because you can imagine the unit square shearing. We can achieve shear with an off-diagonal element:

[ α 1 … β ⋱ ⋮ α i ⋱ α n ] [ x 1 ⋮ x i ⋮ x n ] = x 1 [ α 1 ⋮ ⋮ ⋮ ⋮ ] + ⋯ + x i [ β ⋮ α i ⋮ ⋮ ] + ⋯ + x n [ ⋮ ⋮ ⋮ ⋮ α n ] \begin{bmatrix} \alpha_1 & \dots & \textcolor{#bc2612}{\beta} & & \\ & \ddots & \vdots & & \\ & & \textcolor{#bc2612}{\alpha_i} & & \\ & & & \ddots & \\ & & & & \alpha_n \end{bmatrix} \begin{bmatrix} x_1 \\ \vdots \\ x_i \\ \vdots \\ x_n \end{bmatrix} = x_1 \begin{bmatrix} \textcolor{#11accd}{\alpha_1} \\ \phantom{\vdots} \\ \phantom{\vdots} \\ \phantom{\vdots} \\ \phantom{\vdots} \end{bmatrix} + \dots + x_i \begin{bmatrix} \textcolor{#bc2612}{\beta} \\ \phantom{\vdots} \\ \textcolor{#bc2612}{\alpha_i} \\ \phantom{\vdots} \\ \phantom{\vdots} \end{bmatrix} + \dots + x_n \begin{bmatrix} \phantom{\vdots} \\ \phantom{\vdots} \\ \phantom{\vdots} \\ \phantom{\vdots} \\ \textcolor{#807504}{\alpha_n} \end{bmatrix} ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ ​ α 1 ​ ​ … ⋱ ​ β ⋮ α i ​ ​ ⋱ ​ α n ​ ​ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ ​ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ ​ x 1 ​ ⋮ x i ​ ⋮ x n ​ ​ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ ​ = x 1 ​ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ ​ α 1 ​ ⋮ ⋮ ⋮ ⋮ ​ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ ​ + ⋯ + x i ​ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ ​ β ⋮ α i ​ ⋮ ⋮ ​ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ ​ + ⋯ + x n ​ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ ​ ⋮ ⋮ ⋮ ⋮ α n ​ ​ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ ​

Without the off-diagonal element β \beta β , this transformation would just stretch x 1 x_1 x 1 ​ by α 1 \alpha_1 α 1 ​ . The off-diagonal element means that a transformed vector’s 1 1 1 -st component is a linear combination of β \beta β and α 1 \alpha_1 α 1 ​ . This results in a unit square that is sheared because one dimension is now a function of two dimensions (Figure 4 4 4 ).

The matrix visualized in Figure 1 1 1 is a concrete example of a shear matrix.

Orthogonal matrix

An orthogonal matrix A A A is a square matrix whose columns and rows are orthogonal unit vectors. Let a i \textbf{a}_i a i ​ represent the i i i -th column vector of A A A . Recall that two vectors are orthogonal if the dot product between them is 0 0 0 . Geometrically, this means that if you were to project one vector onto another, it would turn into a point rather than a line (Figure 5 5 5 ).

So the columns a i ⊤ a j = 0 \textbf{a}_i^{\top} \textbf{a}_j = 0 a i ⊤ ​ a j ​ = 0 for all i ≠ j i \neq j i  ​ = j . And since the columns are unit vectors, then a i ⊤ a i = 1 \textbf{a}_i^{\top} \textbf{a}_i = 1 a i ⊤ ​ a i ​ = 1 . An immediate consequence of this is that if a matrix A ∈ R n × n A \in \mathbb{R}^{n \times n} A ∈ R n × n is orthogonal, then:

A A ⊤ = A ⊤ A = I n A A^{\top} = A^{\top} A = I_n A A ⊤ = A ⊤ A = I n ​

If this is not obvious, write out the matrices explicitly as column and row vectors:

A ⊤ A = [ a 1 ⊤ a 2 ⊤ ⋮ a n ⊤ ] [ a 1 a 2 … a n ] = [ 1 1 ⋱ 1 ] = I n A^{\top} A = \left[\begin{array}{c} \textbf{a}_1^{\top} \\ \hline \textbf{a}_2^{\top} \\ \hline \vdots \\ \hline \textbf{a}_n^{\top} \end{array}\right] \left[ \begin{array}{c|c|c|c} \textbf{a}_1 & \textbf{a}_2 & \dots & \textbf{a}_n \end{array} \right] = \begin{bmatrix} 1 & & & \\ & 1 & & \\ & & \ddots & \\ & & & 1 \end{bmatrix} = I_n A ⊤ A = ⎣ ⎢ ⎢ ⎢ ⎢ ⎡ ​ a 1 ⊤ ​ a 2 ⊤ ​ ⋮ a n ⊤ ​ ​ ​ ⎦ ⎥ ⎥ ⎥ ⎥ ⎤ ​ [ a 1 ​ ​ a 2 ​ ​ … ​ a n ​ ​ ] = ⎣ ⎢ ⎢ ⎢ ⎡ ​ 1 ​ 1 ​ ⋱ ​ 1 ​ ⎦ ⎥ ⎥ ⎥ ⎤ ​ = I n ​

But what is the geometric intuition for orthogonal matrices? In words, an orthogonal matrix can rotate or flip a vector space, but it will not stretch it or compress it. But we can make our thinking more rigorous. The key is to observe a few key properties of orthogonal matrices:

1. Angles are preserved

Given a set of vectors, { v 1 , v 2 , … v k } \{\textbf{v}_1, \textbf{v}_2, \dots \textbf{v}_k \} { v 1 ​ , v 2 ​ , … v k ​ } , which we can represent as columns in a matrix V V V , an orthogonal matrix A A A will preserve all the angles between pairs of vectors in this set after the transformation A V AV A V . To see this, let v i ⋅ v j \textbf{v}_i \cdot \textbf{v}_j v i ​ ⋅ v j ​ denote the dot product between vectors v i \textbf{v}_i v i ​ and v j \textbf{v}_j v j ​ . Then,

( A v i ) ⊤ ( A v j ) = v i ⊤ A ⊤ A v j = v i ⊤ v j \begin{aligned} (A \textbf{v}_i)^{\top} (A \textbf{v}_j) &= \textbf{v}_i^{\top} A^{\top} A \textbf{v}_j \\ &= \textbf{v}_i^{\top} \textbf{v}_j \end{aligned} ( A v i ​ ) ⊤ ( A v j ​ ) ​ = v i ⊤ ​ A ⊤ A v j ​ = v i ⊤ ​ v j ​ ​

In words, all angles between pairs of vectors are preserved.

2. Lengths are preserved

Given our same set of vectors V V V , an orthogonal matrix A A A will preserve all lengths of the vectors v ∈ V \textbf{v} \in V v ∈ V after the transformation A V AV A V . This proof is just a small modification of the previous proof:

∥ A v ∥ 2 2 = ( A v ) ⊤ ( A v ) = v ⊤ A ⊤ A v = v ⊤ v = ∥ v ∥ 2 2 \begin{aligned} \lVert A \textbf{v} \lVert_2^2 &= (A \textbf{v})^{\top} (A \textbf{v}) \\ &= \textbf{v}^{\top} A^{\top} A \textbf{v} \\ &= \textbf{v}^{\top} \textbf{v} \\ &= \lVert \textbf{v} \rVert_2^2 \end{aligned} ∥ A v ∥ 2 2 ​ ​ = ( A v ) ⊤ ( A v ) = v ⊤ A ⊤ A v = v ⊤ v = ∥ v ∥ 2 2 ​ ​

In words, the length of any vector in V V V is preserved after transformation.

3. Area is preserved

Note that the determinant of an orthogonal matrix is either 1 1 1 or − 1 -1 − 1 . This is because,

1 = det ⁡ ( I n ) = det ⁡ ( A ⊤ A ) = det ⁡ ( A ⊤ ) det ⁡ ( A ) = ( det ⁡ ( A ) ) 2 1 = \det(I_n) = \det(A^{\top} A) = \det(A^{\top}) \det(A) = (\det(A))^2 1 = det ( I n ​ ) = det ( A ⊤ A ) = det ( A ⊤ ) det ( A ) = ( det ( A ) ) 2

Since the determinant represents the signed factor that the area of an n n n -cube is multiplied by when being transformed by a matrix, a determinant of 1 1 1 or − 1 -1 − 1 means the cube is only rotated or reflected.

To summarize the previous three points: angles, lengths, and areas of a vector space transformed by an orthogonal matrix are all preserved. In my mind, this is a beautiful result. We have a geometric notion of an orthogonal matrix as a function that can only rotate or reflect a vector space, but we can combine this intuition with formal mathematical ideas such as orthogonality of vectors, the definition of the dot product, and the determinant to say something that is mathematically precise.

Composing linear functions

Since f ( g ( x ) ) f(g(x)) f ( g ( x ) ) is linear if both f f f and g g g are linear, we can compose matrix transformations using matrix multiplications. In fact, because of singular value decomposition (SVD), we make a very strong claim: any matrix A ∈ R m × n A \in \mathbb{R}^{m \times n} A ∈ R m × n has a singular value decomposition U Σ V ⊤ U \Sigma V^{\top} U Σ V ⊤ where U ∈ R m × m U \in \mathbb{R}^{m \times m} U ∈ R m × m and V ∈ R n × n V \in \mathbb{R}^{n \times n} V ∈ R n × n are orthogonal matrices and Σ ∈ R m × n \Sigma \in \mathbb{R}^{m \times n} Σ ∈ R m × n is diagonal. Intuitively, this means we can decompose any matrix transformation into simpler transformations such as unitary transformations and diagonal transformations. This falls out of the fact that the image of the unit sphere under any matrix transformation is a hyperellipse.

I want to save SVD for a future post, but let’s look at a simple example of matrix multiplication as function composition from (Paeth, 1986) , who claims but does not prove that any 2 × 2 2 \times 2 2 × 2 rotation matrix can be decomposed into three shear matrices. Following the example in that paper, consider decomposing a rotation matrix R R R and three shear matrices M i ∈ { 1 , 2 , 3 } M_{i \in \{1,2,3\}} M i ∈ { 1 , 2 , 3 } ​ :

[ cos ⁡ ( θ ) − sin ⁡ ( θ ) sin ⁡ ( θ ) cos ⁡ ( θ ) ] ⏞ R = M 3 × M 2 × M 1 \overbrace{\begin{bmatrix} \cos(\theta) & -\sin(\theta) \\ \sin(\theta) & \cos(\theta) \end{bmatrix}}^{R} = M_3 \times M_2 \times M_1 [ cos ( θ ) sin ( θ ) ​ − sin ( θ ) cos ( θ ) ​ ] ​ R ​ = M 3 ​ × M 2 ​ × M 1 ​

M 1 = [ 1 α 0 1 ] M 2 = [ 1 0 β 1 ] M 3 = [ 1 γ 0 1 ] M_1 = \begin{bmatrix} 1 & \alpha \\ 0 & 1 \end{bmatrix} \qquad M_2 = \begin{bmatrix} 1 & 0 \\ \beta & 1 \end{bmatrix} \qquad M_3 = \begin{bmatrix} 1 & \gamma \\ 0 & 1 \end{bmatrix} M 1 ​ = [ 1 0 ​ α 1 ​ ] M 2 ​ = [ 1 β ​ 0 1 ​ ] M 3 ​ = [ 1 0 ​ γ 1 ​ ]

Using a little trigonometry, we can solve for α = − tan ⁡ ( θ 2 ) \alpha = -\tan(\frac{\theta}{2}) α = − tan ( 2 θ ​ ) , β = sin ⁡ ( θ ) \beta = \sin(\theta) β = sin ( θ ) , and γ = − tan ⁡ ( θ 2 ) \gamma = -\tan(\frac{\theta}{2}) γ = − tan ( 2 θ ​ ) . See the Appendix for a derivation. We can sanity check our work visualizing the matrix transformations for a specific θ \theta θ , say θ = π 3 \theta = \frac{\pi}{3} θ = 3 π ​ (Figure 6 6 6 ).

I think this is a really beautiful way to think about matrix multiplication, and it also drives home the utility of a geometrical understanding. For example, image shearing and then rotating a unit square. Now imagine applying the rotation matrix first and then shearing the rotated matrix—be sure to shear with respect to the standard basis vectors, not along an axis parallel with the rotated matrix! You won’t get the same resultant matrix. (It may help to sketch this out.) What this means that matrix multiplication is not necessarily commutative, and this is a property you can visualize rather than just remember.

Properties of matrices

With a geometrical understanding of matrices as linear transformations, many concepts in linear algebra are easier to appreciate. Here are just a concepts that are, in my mind, easier to understand geometrically.

Invertibility

Thinking of a matrix as a geometric transformation or projection, it should be clear that a rectangular matrix cannot be invertible. This is because a rectangular matrix projects vectors into either a higher- or lower-dimensional space. Imagine you found an apple lying on the ground beneath an apple tree. Can you tell me how high it was before it fell to the ground?

The rank of a matrix A A A is the maximal number of linearly independent columns of A A A . Again, if we think of the columns of a matrix as defining where the standard basis vectors land after the transformation, then a low-rank matrix creates linear dependencies between standard basis vectors. The linear dependence between columns means that any projection will map a higher-dimensional vector space to a lower-dimensional vector space.

The null space is the set of all vectors that land on the origin or become null after a transformation. For example, if a 3 × 3 3 \times 3 3 × 3 matrix has rank 2 2 2 , that means it projects all the points in a 3-dimensional space onto a plane. This means there are a line of vectors that all land on the origin. If this is hard to visualize, imagine flattening a cardboard box in which the origin is in the center of the box. As you flatten the box, there must a line of vectors that all collapse to the origin.

Spectral norm

The spectral norm computes the maximum singular value σ 1 \sigma_1 σ 1 ​ of a matrix:

σ 1 = max ⁡ ∥ x ∥ 2 ≠ 0 ∥ A x ∥ 2 ∥ x ∥ 2 \sigma_1 = \max_{\lVert \textbf{x} \rVert_2 \neq \textbf{0}} \frac{\lVert A \textbf{x} \rVert_2}{\lVert \textbf{x} \rVert_2} σ 1 ​ = ∥ x ∥ 2 ​  ​ = 0 max ​ ∥ x ∥ 2 ​ ∥ A x ∥ 2 ​ ​

Since a matrix transforms a vector, we can think of the spectral norm as measuring the maximum amount that a matrix can “stretch” a vector. Many methods and proofs in numerical and randomized linear algebra rely on this norm. For example, algorithms in (Mahoney, 2016) use the spectral norm to bound randomized approximations of matrix multiplication.

Determinant

The determinant has the property that it is multiplicative. That is:

det ⁡ ( A B ) = det ⁡ ( A ) det ⁡ ( B ) \det(AB) = \det(A)\det(B) det ( A B ) = det ( A ) det ( B )

You can easily find formal proofs of this, but let’s convince ourselves that this is at least plausible through geometrical intuition. Consider a scenario in which A A A and B B B are defined as follows:

A = [ 3 0 0 1 ] B = [ 2 0 0 1 ] A = \begin{bmatrix} 3 & 0 \\ 0 & 1 \end{bmatrix} \qquad B = \begin{bmatrix} 2 & 0 \\ 0 & 1 \end{bmatrix} A = [ 3 0 ​ 0 1 ​ ] B = [ 2 0 ​ 0 1 ​ ]

Our geometrical understanding of matrices suggests that matrix A A A dilates e 1 \textbf{e}_1 e 1 ​ by 3 3 3 and matrix B B B dilates e 1 \textbf{e}_1 e 1 ​ by 2 2 2 . Can you see why the determiant is multiplicative (Figure 7 7 7 )?

The determinant of A A A is 3 3 3 , while the determinant of B B B is 2 2 2 . And what is the determinant of A B AB A B ? It is 6 6 6 because it dilates a unit cube by 6 6 6 .

Another cool property of the determinant that is easy to visualize is its sign. The sign of the determinant is positive if the matrix does not change the chirality of the space and negative if it does. This is, I think, easy to visualize (Figure 8 8 8 ).

Imagine a chiral object—that is, an object that cannot be mapped to its mirror image by rotations and translations alone, for example a hand. A matrix transformation on that chiral object that changes its chirality changes the sign of the determinant.

While thinking about these ideas, I came across this lecture by Amritanshu Prasad , who argues at the end of the video for a geometrical understanding:

Most of us think fairly geometrically to start with, and algebra comes as part of training. Also, a lot of mathematics comes from trying to model problems in physics where we really need to think geometrically. So in that sense, a definition that is geometric has much more relationship to the physical world around us and also perhaps gives us a better intuition about the object we’re studying.

Mathematics is a contact sport, and I have no illusions that a geometrical understanding that is not paired with rigorous, numerical understanding is sufficient. It is impossible to deeply understand a mathematical idea if you cannot formalize it. That said, I have found that my ability to “think in linear algebra” has been strengthened by a better geometrical understanding of the material.

Acknowledgements

I thank Philippe Eenens for helpful suggestions for clarifying the notation.

1. Proof that matrices are linear transformations

To prove that a function f f f is linear, we need to show two properties :

• f ( a ) + f ( b ) = f ( a + b ) f(a) + f(b) = f(a + b) f ( a ) + f ( b ) = f ( a + b )
• f ( c a ) = c f ( a ) f(ca) = c f(a) f ( c a ) = c f ( a )

Let A A A be an m × n m \times n m × n vector, so the i i i -th column in A A A , a i \textbf{a}_i a i ​ , is an m m m -vector and there are n n n such vectors. And let v \textbf{v} v and u \textbf{u} u be two n n n -vectors. Then we can express a function f f f as the linear combination of the columns of A A A where the coefficients in are the scalar components in v \textbf{v} v and u \textbf{u} u :

f ( v ) = A v = v 1 a 1 + v 2 a 2 + ⋯ + v n a n f ( u ) = A u = u 1 a 1 + u 2 a 2 + ⋯ + u n a n \begin{aligned} f(\textbf{v}) &= A \textbf{v} = v_1 \textbf{a}_1 + v_2 \textbf{a}_2 + \dots + v_n \textbf{a}_n \\ f(\textbf{u}) &= A \textbf{u} = u_1 \textbf{a}_1 + u_2 \textbf{a}_2 + \dots + u_n \textbf{a}_n \end{aligned} f ( v ) f ( u ) ​ = A v = v 1 ​ a 1 ​ + v 2 ​ a 2 ​ + ⋯ + v n ​ a n ​ = A u = u 1 ​ a 1 ​ + u 2 ​ a 2 ​ + ⋯ + u n ​ a n ​ ​

Proving both properties is straightforward with this representation because we only need to rely on properties of scalar addition and multiplication.

f ( u ) + f ( v ) = A u + A v = u 1 a 1 + u 2 a 2 + ⋯ + u n a n + v 1 a 1 + v 2 a 2 + ⋯ + v n a n = ( u 1 + v 1 ) a 1 + ( u 2 + v 2 ) a 2 + ⋯ + ( u n + v n ) a n = A ( u + v ) = f ( u + v ) \begin{aligned} f(\textbf{u}) + f(\textbf{v}) &= A \textbf{u} + A \textbf{v} \\ &= u_1 \textbf{a}_1 + u_2 \textbf{a}_2 + \dots + u_n \textbf{a}_n + v_1 \textbf{a}_1 + v_2 \textbf{a}_2 + \dots + v_n \textbf{a}_n \\ &= (u_1 + v_1) \textbf{a}_1 + (u_2 + v_2) \textbf{a}_2 + \dots + (u_n + v_n) \textbf{a}_n \\ &= A(\textbf{u} + \textbf{v}) \\ &= f(\textbf{u} + \textbf{v}) \end{aligned} f ( u ) + f ( v ) ​ = A u + A v = u 1 ​ a 1 ​ + u 2 ​ a 2 ​ + ⋯ + u n ​ a n ​ + v 1 ​ a 1 ​ + v 2 ​ a 2 ​ + ⋯ + v n ​ a n ​ = ( u 1 ​ + v 1 ​ ) a 1 ​ + ( u 2 ​ + v 2 ​ ) a 2 ​ + ⋯ + ( u n ​ + v n ​ ) a n ​ = A ( u + v ) = f ( u + v ) ​

f ( c u ) = A ( c u ) = c u 1 a 1 + c u 2 a 2 + ⋯ + c u n a n = c ( u 1 a 1 + u 2 a 2 + ⋯ + u n a n ) = c A ( u ) = c f ( u ) \begin{aligned} f(c\textbf{u}) &= A(c \textbf{u}) \\ &= c u_1 \textbf{a}_1 + c u_2 \textbf{a}_2 + \dots + c u_n \textbf{a}_n \\ &= c(u_1 \textbf{a}_1 + u_2 \textbf{a}_2 + \dots + u_n \textbf{a}_n) \\ &= c A(\textbf{u}) \\ &= c f(\textbf{u}) \end{aligned} f ( c u ) ​ = A ( c u ) = c u 1 ​ a 1 ​ + c u 2 ​ a 2 ​ + ⋯ + c u n ​ a n ​ = c ( u 1 ​ a 1 ​ + u 2 ​ a 2 ​ + ⋯ + u n ​ a n ​ ) = c A ( u ) = c f ( u ) ​

2. Derivation for rotation matrix decomposition

To solve for α \alpha α , β \beta β , and γ \gamma γ in terms of θ \theta θ , let’s first multiply our matrices:

[ 1 α 0 1 ] [ 1 0 β 1 ] ⏞ M 1 × M 2 = [ 1 + α β α β 1 ] \overbrace{\begin{bmatrix} 1 & \alpha \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ \beta & 1 \end{bmatrix}}^{M_1 \times M_2} = \begin{bmatrix} 1 + \alpha \beta & \alpha \\ \beta & 1 \end{bmatrix} [ 1 0 ​ α 1 ​ ] [ 1 β ​ 0 1 ​ ] ​ M 1 ​ × M 2 ​ ​ = [ 1 + α β β ​ α 1 ​ ]

[ 1 + α β α β 1 ] [ 1 γ 0 1 ] ⏞ M 1 × M 2 × M 3 = [ 1 + α β γ + α β γ + α β β γ + 1 ] \overbrace{\begin{bmatrix} 1 + \alpha \beta & \alpha \\ \beta & 1 \end{bmatrix} \begin{bmatrix} 1 & \gamma \\ 0 & 1 \end{bmatrix}}^{M_1 \times M_2 \times M_3} = \begin{bmatrix} 1 + \alpha \beta & \gamma + \alpha \beta \gamma + \alpha \\ \beta & \beta \gamma + 1 \end{bmatrix} [ 1 + α β β ​ α 1 ​ ] [ 1 0 ​ γ 1 ​ ] ​ M 1 ​ × M 2 ​ × M 3 ​ ​ = [ 1 + α β β ​ γ + α β γ + α β γ + 1 ​ ]

We are given that a 2 × 2 2 \times 2 2 × 2 rotation matrix is equivalent to these three shear matrices:

[ cos ⁡ ( θ ) − sin ⁡ ( θ ) sin ⁡ ( θ ) cos ⁡ ( θ ) ] = [ 1 + α β γ + α β γ + α β β γ + 1 ] \begin{bmatrix} \cos(\theta) & - \sin(\theta) \\ \sin(\theta) & \cos(\theta) \end{bmatrix} = \begin{bmatrix} 1 + \alpha \beta & \gamma + \alpha \beta \gamma + \alpha \\ \beta & \beta \gamma + 1 \end{bmatrix} [ cos ( θ ) sin ( θ ) ​ − sin ( θ ) cos ( θ ) ​ ] = [ 1 + α β β ​ γ + α β γ + α β γ + 1 ​ ]

Now let’s solve. Immediately, we have:

β = sin ⁡ ( θ ) \beta = \sin(\theta) β = sin ( θ )

We can use this to solve for α \alpha α :

cos ⁡ ( θ ) = 1 + α β = 1 + α sin ⁡ ( θ ) α = cos ⁡ ( θ ) − 1 sin ⁡ ( θ ) = − 1 − cos ⁡ ( θ ) sin ⁡ ( θ ) = − tan ⁡ ( θ 2 ) \begin{aligned} \cos(\theta) &= 1 + \alpha \beta \\ &= 1 + \alpha \sin(\theta) \\ \alpha &= \frac{\cos(\theta) - 1}{\sin(\theta)} \\ &= -\frac{1 - \cos(\theta)}{\sin(\theta)} \\ &= - \tan\Big(\frac{\theta}{2}\Big) \end{aligned} cos ( θ ) α ​ = 1 + α β = 1 + α sin ( θ ) = sin ( θ ) cos ( θ ) − 1 ​ = − sin ( θ ) 1 − cos ( θ ) ​ = − tan ( 2 θ ​ ) ​

Finally, let’s solve for γ \gamma γ :

cos ⁡ ( θ ) = β γ + 1 = sin ⁡ ( θ ) γ + 1 cos ⁡ ( θ ) − 1 sin ⁡ ( θ ) = γ γ = − 1 − cos ⁡ ( θ ) sin ⁡ ( θ ) = − tan ⁡ ( θ 2 ) \begin{aligned} \cos(\theta) &= \beta \gamma + 1 \\ &= \sin(\theta) \gamma + 1 \\ \frac{\cos(\theta) - 1}{\sin(\theta)} &= \gamma \\ \gamma &= - \frac{1 - \cos(\theta)}{\sin(\theta)} \\ &= - \tan\Big(\frac{\theta}{2}\Big) \end{aligned} cos ( θ ) sin ( θ ) cos ( θ ) − 1 ​ γ ​ = β γ + 1 = sin ( θ ) γ + 1 = γ = − sin ( θ ) 1 − cos ( θ ) ​ = − tan ( 2 θ ​ ) ​

• Trefethen, L. N., & Bau III, D. (1997). Numerical linear algebra (Vol. 50). Siam.
• Paeth, A. W. (1986). A fast algorithm for general raster rotation. Graphics Interface , 86 (5).
• Mahoney, M. W. (2016). Lecture notes on randomized linear algebra. ArXiv Preprint ArXiv:1608.04481 .

• IIT JEE Study Material

A rectangular array of m × n numbers (real or complex) in the form of m horizontal lines (called rows) and n vertical lines (called columns) is called a matrix of order m by n, written as m × n matrix. Such an array is enclosed by [ ] or ( ). In this article, we will learn the meaning of matrices , types of matrices, important formulas, etc.

Download Complete Chapter Notes of Matrices & Determinant Download Now

All Contents in Matrices

Introduction to matrices, types of matrices.

• Matrix Operations
• Adjoint and Inverse of a Matrix
• Rank of a Matrix and Special Matrices
• Solving Linear Equations Using Matrix

An m ×  n matrix is usually written as:

In brief, the above matrix is represented by A = [a ij ] mxn . The numbers a 11 , a 12 , ….. etc., are known as the elements of the matrix A, where a ij belongs to the i th row and j th column and is called the (i, j) th element of the matrix A = [a ij ].

Download this lesson as PDF:- Matrices PDF

Important Formulas for  Matrices 

If A and B are square matrices of order n, and I n is a corresponding unit matrix , then

(a) A(adj.A) = | A | I n = (adj A) A

(b) | adj A | = | A |n -1 (Thus A (adj A) is always a scalar matrix)

(c) adj (adj.A) = | A | n-2 A

\(\begin{array}{l}(e)\ |adj\,(adj.A)|=|A{{|}^{{{(n-1)}^{2}}}}\end{array} \)

(f) adj (AB) = (adj B) (adj A)

(g) adj (A m ) = (adj A) m ,

\(\begin{array}{l}(h)\ adj (kA) = {{k}^{n-1}}(adj. A) ,k\in R\end{array} \)

\(\begin{array}{l}(i)\ adj\left( {{I}_{n}} \right)={{I}_{n}}\end{array} \)

(j) adj 0 = 0

(k) A is symmetric ⇒adj A is also symmetric

(l) A is diagonal ⇒adj A is also diagonal

(m) A is triangular ⇒adj A is also triangular

(n) A is singular ⇒| adj A | = 0

(i) Symmetric matrix: A square matrix A = [a ij ] is called a symmetric matrix if a ij = a ji , for all i, j.

(ii) Skew-symmetric matrix: when a ij = – a ji

(iii) Hermitian and skew – Hermitian matrix: \(\begin{array}{l}A={{A}^{\theta }}\end{array} \) (Hermitian matrix)(A θ  represents conjugate transpose)

(iv) Orthogonal matrix: if AA T = I n = A T A

(v) Idempotent matrix: if A 2 = A

(vi) Involuntary matrix: if A 2 = I or A -1 = A

(vii) Nilpotent matrix:  A square matrix A is nilpotent; if A p  = 0, p is an integer.

Trace of Matrix

The trace of a square matrix is the sum of the elements on the main diagonal.

(i) tr(λA_ = λ tr(A)

(ii) tr(A + B) = tr(A) + tr(B)

(iii) tr(AB) = tr(BA)

Matrix Transpose

\(\begin{array}{l}(iv)\ {{(kA)}^{T}}=k{{\left( A \right)}^{T}} \;\;\;\;\;\; \\ (v)\ {{({{A}_{1}}{{A}_{2}}{{A}_{3}}…….{{A}_{n-1}}{{A}_{n}})}^{T}}=A_{n}^{T}A_{n-1}^{t}……A_{3}^{T}A_{2}^{T}A_{1}^{T}\\\end{array} \)

\(\begin{array}{l}(vi)\ {{I}^{T}}=I \;\;\;\;\;\;\; \\ (vii) tr(A)=t({{A}^{T}})\end{array} \)

Properties of Matrix Multiplication

(i) AB ≠ BA

(ii) (AB)C = A(BC)

(iii) A.(B + C) = A.B + A.C

Adjoint of a Matrix

\(\begin{array}{l}(i)\ A(adj\,A)=(adj\,A)A=|A|{{I}_{n}} \\ (ii)\ |adj\,A|=|A{{|}^{n-1}}\end{array} \)

\(\begin{array}{l}(iii)\ (adj\,\,AB)=(adj\,\,B)(adj\,\,A)\\ (iv)\ adj\,(adj\,A)=|A{{|}^{n-2}}\end{array} \)

Inverse of a Matrix

Order of a matrix.

A matrix which has m rows and n columns is called a matrix of order m x n.

For example, the order of \(\begin{array}{l}\begin{bmatrix}\;\;\; 4\;\;\;\;\;\;\;-1\;\;\;\;\;\;\;5 & & \\ \;\;\;6\;\;\;\;\;\;\;\;\;\;8\;\;\;\;\;-7\end{bmatrix}\end{array} \) matrix is 2 x 3.

Note: (a) The matrix is just an arrangement of certain quantities.

(b) The elements of a matrix may be real or complex numbers . If all the elements of a matrix are real, then the matrix is called a real matrix.

(c) An m x n matrix has m.n elements.

Illustration 1: Construct a 3×4 matrix A = [a ij ], whose elements are given by a ij = 2i + 3j.

Solution: In this problem, I and j are the number of rows and columns, respectively. By substituting the respective values of rows and columns in a ij = 2i + 3j, we can construct the required matrix.

Given a ij = 2i + 3j

so a 11 = 2+3 = 5, a 12 = 2+6 = 8

Similarly, a 13 = 11, a 14 =14, a 21 = 7, a 22 =10, a 23 =13, a 24 =16,a 31 =9, a 32 =12, a 33 =15, a 34 =18

The method for solving this problem is the same as in the above problem.

Trace of a Matrix

Let A = [a ij ] nxn and B = [b ij ] nxn and λ be a scalar,

(i) tr(λA) = λ tr(A) (ii) tr(A + B) = tr(A) + tr(B) (iii) tr(AB) = tr(BA)

Transpose of Matrix

The matrix obtained from a given matrix A by changing its rows into columns or columns into rows is called the transpose of matrix A and is denoted by A T or A’. From the definition, it is obvious that if the order of A is m x n, then the order of A T becomes n x m; For example, transpose of a matrix.

Properties of Transpose of Matrix

(i) (A T ) T = A (ii) (A + B) T = A T + B T (iii) (AB) T = B T A T (iv) (kA) T = k(A) T

(v) (A 1 A 2 A 3 ……A n-1 A n ) T = \(\begin{array}{l}A_{n}^{T}A_{n-1}^{T}…..A_{3}^{T}A_{2}^{T}A_{1}^{T}\end{array} \) (vi) I T = I (vii) tr(A) = tr(A T )

Problems on Matrices

Illustration 3: If \(\begin{array}{l}A=\begin{bmatrix} 1 &-2 &3 \\ -4 & 2 & 5 \end{bmatrix}\ and\ B=\begin{bmatrix} 1 &3 \\ -1&0 \\ 2&4 \end{bmatrix}\end{array} \) . then prove that (AB) T = B T A T .

By obtaining the transpose of AB, i.e., (AB) T and multiplying B T and A T , we can easily get the result.

Here, AB = \(\begin{array}{l}\begin{bmatrix} 1 & -2 &3 \\ -4& 2& 5 \end{bmatrix}  \begin{bmatrix} 1 &3 \\ -1&0 \\ 2& 4 \end{bmatrix}=\begin{bmatrix} 1(1)-2(-1)+3(2) &1(3)-2(0)+3(4) \\ -4(1)+2(-1)+5(2) &-4(3)+2(0)+5(4) \end{bmatrix} = \begin{bmatrix} 9 &15 \\ 4& 8 \end{bmatrix}\end{array} \) .

Illustration 4: If \(\begin{array}{l}A=\begin{bmatrix} 5 &-1 &3 \\ 0& 1& 2 \end{bmatrix}\ and\ B=\begin{bmatrix} 0 &2 &3 \\ 1& -1 &4 \end{bmatrix}\end{array} \) . Then what is (B’)’A’ equal to?

In this problem, we use the properties of the transpose of a matrix to get the required result.

We have = \(\begin{array}{l}{({B}’)}'{A}’ =B{A}’=\begin{bmatrix} 0 &2 &3 \\ 1& -1 &4 \end{bmatrix}\begin{bmatrix} 5 &0 \\ -1&1 \\ 3& 2 \end{bmatrix}=\begin{bmatrix} 7 & 8\\ 18& 7 \end{bmatrix}\end{array} \) .

is a singular matrix, then find x. Verify whether AA T = I for that value of x.

Using the condition of a singular matrix, i.e., |A| = 0, we get the value of x and then by substituting the value of x in matrix A and multiplying it by its transpose, we will obtain the required result.

R 3 –> R 3 + R 2

C 2   → C 2 -C 3

Here, x = 0, 3.

Note: The simple way to solve is that if A is a singular matrix , then |A| = 0 and |A T | = 0. But |I| is 1.

Hence, AA T ≠ I if |A| = 0.

where a, b, c are positive real numbers such that abc = 1 and A T A = I, then find the value of a 3 + b 3 + c 3 .

Given: abc = 1 and A T A = I

Interchanging rows and columns,

A T A = I (given)

Solving the above equation, we have

(a 2 + b 2 + c 2 ) = 1 and ab + bc + ca = 0  . …..(i)

We know, (a + b + c) 2 = (a 2 + b 2 + c 2 ) + 2(ab + bc + ca)

or (a + b + c) = 1  ….(ii)

Again ,we have (a 3 + b 3 + c 3 -3abc) = (a + b + c) (a 2 + b 2 + c 2 -ab – bc – ca)

Since abc = 1

Using  (i) and (ii), we have

(a 3 + b 3 + c 3 -3) = 1

or a 3 + b 3 + c 3 =4

then find the values of a, b, c, x, y and z.

As the two matrices are equal, their corresponding elements are also equal. Therefore, by equating the corresponding elements of the given matrices, we will obtain the values of a, b, c, x, y and z.

Comparing both sides, we get [x + 3 = 0] ⇒ x = – 3

z + 4 = 6  ⇒ z = 6 – 4 ⇒ z = 2

2y – 7 = 3y – 2 ⇒ 2y – 3y = -2 + 7 ⇒ -y = 5 ⇒ y = -5

a – 1 = -3 ⇒ a = -3 + 1 ⇒ a = -2

b – 3 = 2b + 4 ⇒ b – 2b = 4 + 3 ⇒ -b = 7 ⇒ b = -7

2c + z = 0 ⇒ 2c + 2 = 0 ⇒ 2c = -2 ⇒ c = -2/2 ⇒ c = -1

a = -2, b = -7, c = -1, x = -3, y = -5 and z = 2

Determinants

Matrices and Determinants Previous Year Questions

Video Lessons

Important Questions for JEE Matrices and Determinants

Matrices and Determinants Revision for JEE – Part 1

Matrices and Determinants Revision for JEE – Part 2

Matrices and Determinants Revision for JEE – Part 3

Matrices and Determinants Revision for JEE – Part 4

Toughest JEE Advanced Problems from Matrices and Determinants

Top JEE Advanced Questions from Matrices and Determinants

Most Difficult Matrices and Determinants Problems for JEE Advanced 2022

Frequently Asked Questions on Matrices

What is meant by a null matrix.

A null matrix is a matrix whose all the elements are zero.

What is the transpose of a matrix?

The transpose of a matrix is the matrix obtained by interchanging its rows into columns or columns into rows.

What is meant by a diagonal matrix?

A diagonal matrix is a matrix in which the entries outside the main diagonal are all zeros.

What is meant by a square matrix?

If the number of rows and columns in a matrix is equal, then it is called a square matrix.

Give the formula to find the inverse of a matrix A.

The inverse of a matrix A is given by A -1 = Adj A/det A. Here, adj A is the adjoint of matrix A, and det A is the determinant of A.

What do you mean by Hermitian matrix?

If a square matrix is equal to its conjugate transpose, then that matrix is called a Hermitian matrix.

What do you mean by conjugate matrix?

The conjugate matrix of matrix A is found by replacing the corresponding elements of matrix A with its conjugate complex numbers.

What do you mean by a skew-symmetric matrix?

A skew-symmetric matrix is a matrix whose transpose is equal to the negative of the matrix. If A is skew-symmetric, then A T = -A.

Put your understanding of this concept to test by answering a few MCQs. Click ‘Start Quiz’ to begin!

Select the correct answer and click on the “Finish” button Check your score and answers at the end of the quiz

Visit BYJU’S for all JEE related queries and study materials

Your result is as below

Request OTP on Voice Call

Leave a Comment Cancel reply

Your Mobile number and Email id will not be published. Required fields are marked *

Post My Comment

Useful for making project file

• Share Share

Register with Aakash BYJU'S & Download Free PDFs

Register with byju's & watch live videos.

Linear Algebra: A second course, featuring proofs and Python

Sean Fitzpatrick

Section 5.1 The matrix of a linear transformation

Exercise 5.1.1 ..

• \(m\times n\)
• Correct! We need to be able to multiply on the right by an \(n\times 1\) column vector, and get an \(m\times 1\) column vector as output.
• \(n\times m\)
• The domain of \(T_A\) is \(\R^n\text{,}\) and the product \(A\xx\) is only defined if the number of columns ( \(m\) ) is equal to the dimension of the domain.
• \(m\times m\)
• \(n\times n\)
• Although the product \(A\xx\) would be defined in this case, the result would be a vector in \(\R^n\text{,}\) and we want a vector in \(\R^m\text{.}\)

Exercise 5.1.2 .

Definition 5.1.3 . the matrix \(m_{db}(t)\) of a linear map., exercise 5.1.4 ., example 5.1.5 . working with the matrix of a transformation., theorem 5.1.6 ., exercise 5.1.8 ., theorem 5.1.9 ..

Let \(\xx\in U\text{.}\) Then \(C_{B_3}(ST(\xx)) = M_{B_3B_1}(ST)C_{B_1}(\xx)\text{.}\) On the other hand, \begin{align*} M_{B_3B_2}(S)M_{B_2B_1}(T)C_{B_1}(\xx) \amp = M_{B_3B_2}(S)(C_{B_2}(T(\xx)))\\ \amp = C_{B_3}(S(T(\xx))) = C_{B_3}(ST(\xx))\text{.} \end{align*} Since \(C_{B_3}\) is invertible, the result follows.

• \(T:V\to W\) is an isomorphism if and only if \(M_{DB}(T)\) is invertible for some (and hence, all) choice of bases \(B\) of \(V\) and \(D\) of \(W\text{.}\)
• The rank of \(T\) is equal to the rank of \(M_{DB}(T)\) (and this does not depend on the choice of basis).
• The kernel of \(T\) is isomorphic to the nullspace of \(M_{DB}(T)\text{.}\)

Exercises Exercises

• school Campus Bookshelves
• menu_book Bookshelves
• perm_media Learning Objects
• login Login
• how_to_reg Request Instructor Account
• hub Instructor Commons
• Download Page (PDF)
• Download Full Book (PDF)
• Periodic Table
• Physics Constants
• Scientific Calculator
• Reference & Cite
• Tools expand_more
• Readability

selected template will load here

This action is not available.

1.6: Example of matrix representation method and choice of basis

• Last updated
• Save as PDF
• Page ID 28665

• Graeme Ackland
• University of Edinburgh

In practical quantum problems, we almost always describe the state of the system in terms of some basis set. Consider a simple spin 1/2 system, choosing as basis states \(S_z = \pm \frac{1}{2}\). Consider this system in a magnetic field pointing in the \(x\) direction, the operator corresponding to this is \(\mu B \hat{S}_x\). We wish to find the eigenstates and eigenenergies.

Evaluating the required matrix elements such as \(\langle S_z = \frac{1}{2} |\mu B\hat{S}_x | S_z = \frac{1}{2} \rangle\) (see QP3) gives a matrix:

\[\begin{pmatrix} 0 & \mu B/2 \\ \mu B/2 & 0 \end{pmatrix} \nonumber\]

The normalised eigenvectors of this matrix are \((\sqrt{\frac{1}{2}}, \sqrt{\frac{1}{2}})\) and \((\sqrt{\frac{1}{2}}, -\sqrt{\frac{1}{2}})\) with eigenvalues \((\mu B/2)\) and \((-\mu B/2)\). Of course these represent the eigenstates \(|S_x = \pm \frac{1}{2} \rangle\) in the basis of \(|S_z = \pm \frac{1}{2} \rangle\):

\[|S_x = \pm \frac{1}{2} \rangle = \left[|S_z = \frac{1}{2} \rangle \pm |S_z = -\frac{1}{2} \rangle \right] / \sqrt{2} \nonumber\]

Had we chosen \(|S_y = \pm \frac{1}{2} \rangle\) as our basis set, then the matrix would have been:

\[\begin{pmatrix} 0 & -i\mu B/2 \\ i\mu B/2 & 0 \end{pmatrix} \nonumber\]

Once again, the eigenvalues of this matrix are \((\mu B/2)\) and \((-\mu B/2)\), as they must be since these are the measurable quantities. Coincidently, the eigenvectors in this basis set are also \((\sqrt{\frac{1}{2}}, \sqrt{\frac{1}{2}})\) and \((\sqrt{\frac{1}{2}}, -\sqrt{\frac{1}{2}})\).

Had we chosen \(|S_x = \pm \frac{1}{2} \rangle\) as our basis set in the first place, the problem would have been much simplified. The matrix would then be:

\[\begin{pmatrix} \mu B/2 & 0 \\ 0 & -\mu B/2 \end{pmatrix} \nonumber\]

Once again, the eigenvalues of this matrix are \((\mu B/2)\) and \((-\mu B/2)\), and now the eigenvectors are (1,0) and (0,1): i.e. the eigenstates are simply the basis states.

• school Campus Bookshelves
• menu_book Bookshelves
• perm_media Learning Objects
• login Login
• how_to_reg Request Instructor Account
• hub Instructor Commons
• Download Page (PDF)
• Download Full Book (PDF)
• Periodic Table
• Physics Constants
• Scientific Calculator
• Reference & Cite
• Tools expand_more
• Readability

selected template will load here

This action is not available.

6.4: Matrices of Relations

• Last updated
• Save as PDF
• Page ID 80524

• Al Doerr & Ken Levasseur
• University of Massachusetts Lowell

We have discussed two of the many possible ways of representing a relation, namely as a digraph or as a set of ordered pairs. In this section we will discuss the representation of relations by matrices.

Representing a Relation with a Matrix

Definition \(\PageIndex{1}\): Adjacency Matrix

Let \(A = \{a_1,a_2,\ldots , a_m\}\) and \(B= \{b_1,b_2,\ldots , b_n\}\) be finite sets of cardinality \(m\) and \(n\text{,}\) respectively. Let \(r\) be a relation from \(A\) into \(B\text{.}\) Then \(r\) can be represented by the \(m\times n\) matrix \(R\) defined by

\begin{equation*} R_{ij}= \left\{ \begin{array}{cc} 1 & \textrm{ if } a_i r b_j \\ 0 & \textrm{ otherwise} \\ \end{array}\right. \end{equation*}

\(R\) is called the adjacency matrix (or the relation matrix) of \(r\text{.}\)

Example \(\PageIndex{1}\): A Simple Example

Let \(A = \{2, 5, 6\}\) and let \(r\) be the relation \(\{(2, 2), (2, 5), (5, 6), (6, 6)\}\) on \(A\text{.}\) Since \(r\) is a relation from \(A\) into the same set \(A\) (the \(B\) of the definition), we have \(a_1= 2\text{,}\) \(a_2=5\text{,}\) and \(a_3=6\text{,}\) while \(b_1= 2\text{,}\) \(b_2=5\text{,}\) and \(b_3=6\text{.}\) Next, since

• \(2 r 2\text{,}\) we have \(R_{11}= 1\)
• \(2 r 5\text{,}\) we have \(R_{12}= 1\)
• \(5 r 6\text{,}\) we have \(R_{23}= 1\)
• \(6 r 6\text{,}\) we have \(R_{33}= 1\)

All other entries of \(R\) are zero, so

\begin{equation*} R =\left( \begin{array}{ccc} 1 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \\ \end{array} \right) \end{equation*}

Composition as Matrix Multiplication

From the definition of \(r\) and of composition, we note that

\begin{equation*} r^2 = \{(2, 2), (2, 5), (2, 6), (5, 6), (6, 6)\} \end{equation*}

The adjacency matrix of \(r^2\) is

\begin{equation*} R^2 =\left( \begin{array}{ccc} 1 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \\ \end{array} \right)\text{.} \end{equation*}

We do not write \(R^2\) only for notational purposes. In fact, \(R^2\) can be obtained from the matrix product \(R R\text{;}\) however, we must use a slightly different form of arithmetic.

Definition \(\PageIndex{2}\): Boolean Arithmetic

Boolean arithmetic is the arithmetic defined on \(\{0,1\}\) using Boolean addition and Boolean multiplication, defined by

Table \(\PageIndex{1}\)

Notice that from Chapter 3 , this is the “arithmetic of logic,” where \(+\) replaces “or” and \(\cdot\) replaces “and.”

Example \(\PageIndex{2}\): Composition by Multiplication

Suppose that \(R=\left( \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{array} \right)\) and \(S=\left( \begin{array}{cccc} 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ \end{array} \right)\text{.}\) Then using Boolean arithmetic, \(R S =\left( \begin{array}{cccc} 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ \end{array} \right)\) and \(S R=\left( \begin{array}{cccc} 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ \end{array} \right)\text{.}\)

Theorem \(\PageIndex{1}\): Composition is Matrix Multiplication

Let \(A_1\text{,}\) \(A_2\text{,}\) and \(A_3\) be finite sets where \(r_1\) is a relation from \(A_1\) into \(A_2\) and \(r_2\) is a relation from \(A_2\) into \(A_3\text{.}\) If \(R_1\) and \(R_2\) are the adjacency matrices of \(r_1\) and \(r_2\text{,}\) respectively, then the product \(R_1R_2\) using Boolean arithmetic is the adjacency matrix of the composition \(r_1r_2\text{.}\)

Remark: A convenient help in constructing the adjacency matrix of a relation from a set \(A\) into a set \(B\) is to write the elements from \(A\) in a column preceding the first column of the adjacency matrix, and the elements of \(B\) in a row above the first row. Initially, \(R\) in Example \(\PageIndex{1}\) would be

\begin{equation*} \begin{array}{cc} & \begin{array}{ccc} 2 & 5 & 6 \\ \end{array} \\ \begin{array}{c} 2 \\ 5 \\ 6 \\ \end{array} & \left( \begin{array}{ccc} & & \\ & & \\ & & \\ \end{array} \right) \\ \end{array} \end{equation*}

To fill in the matrix, \(R_{ij}\) is 1 if and only if \(\left(a_i,b_j\right) \in r\text{.}\) So that, since the pair \((2, 5) \in r\text{,}\) the entry of \(R\) corresponding to the row labeled 2 and the column labeled 5 in the matrix is a 1.

Example \(\PageIndex{3}\): Relations and Information

This final example gives an insight into how relational data base programs can systematically answer questions pertaining to large masses of information. Matrices \(R\) (on the left) and \(S\) (on the right) define the relations \(r\) and \(s\) where \(a r b\) if software \(a\) can be run with operating system \(b\text{,}\) and \(b s c\) if operating system \(b\) can run on computer \(c\text{.}\)

\begin{equation*} \begin{array}{cc} \begin{array}{cc} & \begin{array}{cccc} \text{OS1} & \text{OS2} & \text{OS3} & \text{OS4} \end{array} \\ \begin{array}{c} \text{P1} \\ \text{P2} \\ \text{P3} \\ \text{P4} \end{array} & \left( \begin{array}{cccc} 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{array} \right) \end{array} \begin{array}{cc} & \begin{array}{ccc} \text{C1} & \text{C2} & \text{C3} \end{array} \\ \begin{array}{c} \text{OS1} \\ \text{OS2} \\ \text{OS3} \\ \text{OS4} \\ \end{array} & \left( \begin{array}{ccc} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 1 \end{array} \right) \end{array} \end{array} \end{equation*}

Although the relation between the software and computers is not implicit from the data given, we can easily compute this information. The matrix of \(rs\) is \(RS\text{,}\) which is

\begin{equation*} \begin{array}{cc} & \begin{array}{ccc} \text{C1} & \text{C2} & \text{C3} \end{array} \\ \begin{array}{c} \text{P1} \\ \text{P2} \\ \text{P3} \\ \text{P4} \end{array} & \left( \begin{array}{ccc} 1 & 1 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 1 \end{array} \right) \end{array} \end{equation*}

This matrix tells us at a glance which software will run on the computers listed. In this case, all software will run on all computers with the exception of program P2, which will not run on the computer C3, and programs P3 and P4, which will not run on the computer C1.

Exercise \(\PageIndex{1}\)

Let \(A_1 = \{1,2, 3, 4\}\text{,}\) \(A_2 = \{4, 5, 6\}\text{,}\) and \(A_3 = \{6, 7, 8\}\text{.}\) Let \(r_1\) be the relation from \(A_1\) into \(A_2\) defined by \(r_1 = \{(x, y) \mid y - x = 2\}\text{,}\) and let \(r_2\) be the relation from \(A_2\) into \(A_3\) defined by \(r_2 = \{(x, y) \mid y - x = 1\}\text{.}\)

• Determine the adjacency matrices of \(r_1\) and \(r_2\text{.}\)
• Use the definition of composition to find \(r_1r_2\text{.}\)
• Verify the result in part b by finding the product of the adjacency matrices of \(r_1\) and \(r_2\text{.}\)
• \(\begin{array}{cc} & \begin{array}{ccc} 4 & 5 & 6 \\ \end{array} \\ \begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ \end{array} & \left( \begin{array}{ccc} 0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) \\ \end{array}\) and \(\begin{array}{cc} & \begin{array}{ccc} 6 & 7 & 8 \\ \end{array} \\ \begin{array}{c} 4 \\ 5 \\ 6 \\ \end{array} & \left( \begin{array}{ccc} 0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{array} \right) \\ \end{array}\)
• \(\displaystyle r_1r_2 =\{(3,6),(4,7)\}\)
• \(\displaystyle \begin{array}{cc} & \begin{array}{ccc} 6 & 7 & 8 \\ \end{array} \\ \begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ \end{array} & \left( \begin{array}{ccc} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{array} \right) \\ \end{array}\)

Exercise \(\PageIndex{2}\)

• Determine the adjacency matrix of each relation given via the digraphs in Exercise 6.3.3 of Section 6.3 .
• Using the matrices found in part (a) above, find \(r^2\) of each relation in Exercise 6.3.3 of Section 6.3 .
• Find the digraph of \(r^2\) directly from the given digraph and compare your results with those of part (b).

Exercise \(\PageIndex{3}\)

Suppose that the matrices in Example \(\PageIndex{2}\) are relations on \(\{1, 2, 3, 4\}\text{.}\) What relations do \(R\) and \(S\) describe?

Table \(\PageIndex{2}\)

Exercise \(\PageIndex{4}\)

Let \(D\) be the set of weekdays, Monday through Friday, let \(W\) be a set of employees \(\{1, 2, 3\}\) of a tutoring center, and let \(V\) be a set of computer languages for which tutoring is offered, \(\{A(PL), B(asic), C(++), J(ava), L(isp), P(ython)\}\text{.}\) We define \(s\) (schedule) from \(D\) into \(W\) by \(d s w\) if \(w\) is scheduled to work on day \(d\text{.}\) We also define \(r\) from \(W\) into \(V\) by \(w r l\) if \(w\) can tutor students in language \(l\text{.}\) If \(s\) and \(r\) are defined by matrices

\begin{equation*} S = \begin{array}{cc} & \begin{array}{ccc} 1 & 2 & 3 \\ \end{array} \\ \begin{array}{c} M \\ T \\ W \\ R \\ F \\ \end{array} & \left( \begin{array}{ccc} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 1 & 0 \\ \end{array} \right) \\ \end{array} \textrm{ and }R= \begin{array}{cc} & \begin{array}{cccccc} A & B & C & J & L & P \\ \end{array} \\ \begin{array}{c} 1 \\ 2 \\ 3 \\ \end{array} & \left( \begin{array}{cccccc} 0 & 1 & 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 \\ \end{array} \right) \\ \end{array} \end{equation*}

• compute \(S R\) using Boolean arithmetic and give an interpretation of the relation it defines, and
• compute \(S R\) using regular arithmetic and give an interpretation of what the result describes.

Exercise \(\PageIndex{5}\)

How many different reflexive, symmetric relations are there on a set with three elements?

Consider the possible matrices.

The diagonal entries of the matrix for such a relation must be 1. When the three entries above the diagonal are determined, the entries below are also determined. Therefore, there are \(2^3\) fitting the description.

Exercise \(\PageIndex{6}\)

Let \(A = \{a, b, c, d\}\text{.}\) Let \(r\) be the relation on \(A\) with adjacency matrix \(\begin{array}{cc} & \begin{array}{cccc} a & b & c & d \\ \end{array} \\ \begin{array}{c} a \\ b \\ c \\ d \\ \end{array} & \left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ \end{array} \right) \\ \end{array}\)

• Explain why \(r\) is a partial ordering on \(A\text{.}\)
• Draw its Hasse diagram.

Exercise \(\PageIndex{7}\)

Define relations \(p\) and \(q\) on \(\{1, 2, 3, 4\}\) by \(p = \{(a, b) \mid \lvert a-b\rvert=1\}\) and \(q=\{(a,b) \mid a-b \textrm{ is even}\}\text{.}\)

• Represent \(p\) and \(q\) as both graphs and matrices.
• Determine \(p q\text{,}\) \(p^2\text{,}\) and \(q^2\text{;}\) and represent them clearly in any way.
• \(\begin{array}{cc} & \begin{array}{cccc} 1 & 2 & 3 & 4 \\ \end{array} \\ \begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ \end{array} & \left( \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{array} \right) \\ \end{array}\) and \(\begin{array}{cc} & \begin{array}{cccc} 1 & 2 & 3 & 4 \\ \end{array} \\ \begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ \end{array} & \left( \begin{array}{cccc} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ \end{array} \right) \\ \end{array}\)
• \(P Q= \begin{array}{cc} & \begin{array}{cccc} 1 & 2 & 3 & 4 \\ \end{array} \\ \begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ \end{array} & \left( \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{array} \right) \\ \end{array}\) \(P^2 =\text{ } \begin{array}{cc} & \begin{array}{cccc} 1 & 2 & 3 & 4 \\ \end{array} \\ \begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ \end{array} & \left( \begin{array}{cccc} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{array} \right) \\ \end{array}\)\(=Q^2\)

Exercise \(\PageIndex{8}\)

• Prove that if \(r\) is a transitive relation on a set \(A\text{,}\) then \(r^2 \subseteq r\text{.}\)
• Find an example of a transitive relation for which \(r^2\neq r\text{.}\)

Exercise \(\PageIndex{9}\)

We define \(\leq\) on the set of all \(n\times n\) relation matrices by the rule that if \(R\) and \(S\) are any two \(n\times n\) relation matrices, \(R \leq S\) if and only if \(R_{ij} \leq S_{ij}\) for all \(1 \leq i, j \leq n\text{.}\)

• Prove that \(\leq\) is a partial ordering on all \(n\times n\) relation matrices.
• Prove that \(R \leq S \Rightarrow R^2\leq S^2\) , but the converse is not true.
• If \(R\) and \(S\) are matrices of equivalence relations and \(R \leq S\text{,}\) how are the equivalence classes defined by \(R\) related to the equivalence classes defined by \(S\text{?}\)
• Reflexive: \(R_{ij}=R_{ij}\) for all \(i\), \(j\), therefore \(R_{ij}\leq R_{ij}\) Antisymmetric: Assume \(R_{ij}\leq S_{ij}\) and \(S_{ij}\leq R_{ij}\) for all \(1\leq i\), \(j\leq n\). Therefore, \(R_{ij}=S_{ij}\) for all \(1\leq i\), \(j\leq n\) and so \(R=S\) Transitive: Assume \(R,\: S\), and \(T\) are matrices where \(R_{ij}\leq S_{ij}\) and \(S_{ij}\leq T_{ij}\), for all \(1\leq i\), \(j\leq n\). Then \(R_{ij}\leq T_{ij}\) for all \(1\leq i\), \(j\leq n\), and so \(R\leq T\).
• \[\begin{aligned}(R^{2})_{ij}&=R_{i1}R_{1j}+R_{i2}R_{2j}+\cdots +R_{in}R_{nj} \\ &\leq S_{i1}S_{1j}+S_{i2}S_{2j}+\cdots +S_{in}S_{nj} \\ &=(S^{2})_{ij}\Rightarrow R^{2}\leq S^{2}\end{aligned}\] To verify that the converse is not true we need only one example. For \(n=2\), let \(R_{12}=1\) and all other entries equal \(0\), and let \(S\) be the zero matrix. Since \(R^{2}\) and \(S^{2}\) are both the zero matrix, \(R^{2}\leq S^{2}\), but since \(R_{12}>S_{12}\), \(R\leq S\) is false.
• The matrices are defined on the same set \(A=\{a_1,\: a_2,\cdots ,a_n\}\). Let \(c(a_{i})\), \(i=1,\: 2,\cdots, n\) be the equivalence classes defined by \(R\) and let \(d(a_{i}\)) be those defined by \(S\). Claim: \(c(a_{i})⊆ d(a_{i})\). \[\begin{aligned}a_{j}\in c(a_{i})&\Rightarrow a_{i}ra_{j} \\ &\Rightarrow R_{ij}=1\Rightarrow S_{ij}=1 \\ &\Rightarrow a_{i}sa_{j} \\ &\Rightarrow a_{j}\in d(a_{i})\end{aligned}\]

• Data Structures
• Linked List
• Binary Tree
• Binary Search Tree
• Segment Tree
• Disjoint Set Union
• Fenwick Tree
• Red-Black Tree
• Advanced Data Structures

Sparse Matrix and its representations | Set 1 (Using Arrays and Linked Lists)

• Sparse Matrix and its representations | Set 2 (Using List of Lists and Dictionary of keys)
• Sparse Matrix Representations | Set 3 ( CSR )
• Generate matrix from given Sparse Matrix using Linked List and reconstruct the Sparse Matrix
• Counting sets of 1s and 0s in a binary matrix
• Count number of 1's at specific position in a Matrix
• Python Program to Check if a given matrix is sparse or not
• Minimum number of 1s present in a submatrix of given dimensions in a Binary Matrix
• Check if a given matrix is sparse or not
• C++ Program to Check if a given matrix is sparse or not
• Sum of numbers obtained by the count of set and non-set bits in diagonal matrix elements
• Count positions in Binary Matrix having equal count of set bits in corresponding row and column
• What is meant by Sparse Array?
• Sparse Matrix in Python using Dictionary
• How to Create a Sparse Matrix in Python
• Python program to Convert a Matrix to Sparse Matrix
• How to reduce dimensionality on Sparse Matrix in Python?
• Java Program to Determine if a given Matrix is a Sparse Matrix
• Sparse Coding with a Precomputed Dictionary in Scikit Learn
• How to Convert Sparse Matrix to Dense Matrix in R?
• Merge Sort - Data Structure and Algorithms Tutorials
• Must Do Coding Questions for Companies like Amazon, Microsoft, Adobe, ...
• QuickSort - Data Structure and Algorithm Tutorials
• Bubble Sort - Data Structure and Algorithm Tutorials
• Tree Traversal Techniques - Data Structure and Algorithm Tutorials
• Binary Search - Data Structure and Algorithm Tutorials
• Insertion Sort - Data Structure and Algorithm Tutorials
• Selection Sort – Data Structure and Algorithm Tutorials
• Understanding the basics of Linked List
• Breadth First Search or BFS for a Graph

A matrix is a two-dimensional data object made of m rows and n columns, therefore having total m x n values. If most of the elements of the matrix have 0 value , then it is called a sparse matrix.

Why to use Sparse Matrix instead of simple matrix ?

• Storage: There are lesser non-zero elements than zeros and thus lesser memory can be used to store only those elements.
• Computing time: Computing time can be saved by logically designing a data structure traversing only non-zero elements..

Example: 

Representing a sparse matrix by a 2D array leads to wastage of lots of memory as zeroes in the matrix are of no use in most of the cases. So, instead of storing zeroes with non-zero elements, we only store non-zero elements. This means storing non-zero elements with triples- (Row, Column, value).  

Sparse Matrix Representations can be done in many ways following are two common representations: 

• Array representation
• Linked list representation

Method 1: Using Arrays:

2D array is used to represent a sparse matrix in which there are three rows named as 

• Row: Index of row, where non-zero element is located
• Column: Index of column, where non-zero element is located
• Value: Value of the non zero element located at index – (row,column)

Implementation:

Time Complexity:   O(NM), where N is the number of rows in the sparse matrix, and M is the number of columns in the sparse matrix.

Auxiliary Space: O(NM), where N is the number of rows in the sparse matrix, and M is the number of columns in the sparse matrix.

Method 2: Using Linked Lists In linked list, each node has four fields. These four fields are defined as: 

• Next node: Address of the next node

Time Complexity:   O(N*M), where N is the number of rows in the sparse matrix, and M is the number of columns in the sparse matrix. Auxiliary Space: O(K), where K is the number of non-zero elements in the array.

Other representations:  

As a Dictionary where row and column numbers are used as keys and values are matrix entries. This method saves space but sequential access of items is costly.

As a list of list . The idea is to make a list of rows and every item of list contains values. We can keep list items sorted by column numbers. Sparse Matrix and its representations | Set 2 (Using List of Lists and Dictionary of keys)

Please Login to comment...

Similar reads.

Improve your Coding Skills with Practice

What kind of Experience do you want to share?