Matrices: Introduction

Let’s understand the Matrices pattern, its real-world applications, and some problems we can solve with it.

We'll cover the following

Overview#

A matrix is a group of numbers arranged in rows and columns in a rectangular pattern. In computer science, matrixes are represented by 2D arrays with dimensions m×nm \times n, where mm is the number of rows, and nn is the number of columns. Each element in the matrix can be accessed using the array indexes. The first index represents the row, and the second index represents the column. For example, matrix[i][j]matrix[i][j] is an element from the ithi^{th} row and the jthj^{th} column of the matrix.

Most of the problems requiring matrixes can be solved using the following operations:

  • Matrix transformations: A few transformations are scaling, translation, rotation, and reflection.

  • Matrix traversals: A few matrix traversals are simple, spiral, and diagonal traversals, as illustrated below.

We use matrixes when we need to:

  • Process the digital images. An image can be represented as a matrix, where each element of the matrix represents a pixel of the image. We can modify the images by applying different matrix transformations. For example, we can change color, brightness, or orientation of the images.

  • Represent a graph as an adjacency matrix where each row represents a vertex and each column represents an edge.

  • Store results of the subproblems calculated while solving a problem using dynamic programming.

  • Solve different mathematical equations—for example, various problems related to linear algebra.

  • Implement a grid game, such as chess, Candy Crush, Sudoku, Snake, or Tic-Tac-Toe.

Examples#

The following examples illustrate some problems that can be solved with these approaches:

Created with Fabric.js 3.6.6 True Input Matrix: Input Matrix: False 5 9 4 1 2 5 9 4 3 2 5 9 5 2 3 2 2 3 9 2 2 Toeplitz MatrixGiven an m x n matrix, return TRUE if the matrix is Toeplitz. Otherwise, return FALSE.A matrix is Toeplitz if every descending diagonal from left to right (or basically every left diagonal) has the same elements.

1 of 2

Created with Fabric.js 3.6.6 Input Matrix: 1 1 0 1 0 1 0 0 0 1 0 0 0 1 0 1 1 1 0 1 1 1 0 1 0 0 0 Flipped Matrix: Final Matrix (Inverted): Flip and Invert an ImageGiven an n x n binary image, flip it horizontally, invert it, and return the final image.• To flip an image horizontally means that each row of the image is reversed, that is, by rotating each row 90 degrees clockwise about y-axis.• To invert an image means that each 0 is replaced by 1, and each 1 is replaced by 0.

2 of 2

Does my problem match this pattern?#

Yes, if the following condition is fulfilled:

  • The input data is given as a 2D array.

No, if the following conditions are fulfilled:

  • The input data is not given as a 2D array.

  • The input data is given as a 2D array, but it falls under some other pattern and can’t be solved by matrix operations. For example, graphs, dynamic programming, etc.

Real-world problems#

Many problems in the real world share the matrix transformation pattern. Let’s look at some examples:

  • In the video game industry, where matrixes play a major role in the manipulation of animations.

  • In Google's page ranking algorithms, where it is difficult to maintain a Google matrix representing links between web pages.

  • In cryptography algorithms, such as a Hill cipher, which uses matrix multiplication to encrypt and decrypt messages.

Strategy time!#

Match the problems that can be solved using the matrix transformation pattern.

Note: Select a problem in the left-hand column by clicking it, and then click one of the two options in the right-hand column.

Match The Answer
Select an option from the left-hand side

Rotate an image.

Explanation

Matrices

Find the longest palindromic sequence in a given string.

Explanation

Some other pattern

Implement a basic calculator.

Explanation

Given an m×nm \times n map of a server center, return the number of servers that communicate with any other server.

Explanation

Solution: Valid Parentheses

Spiral Matrix