Matrices

John

The following are some notes taken during a lecture.

Matrices: Overview

  • Matrices are useful discrete structures that can be used in many ways. For example, they are used to:
    • Describe certain types of functions known as linear transformations.
    • Express which vertices of a graph are connected by edges.
    • In Machine Learning, Data Mining, and Information Retrieval, they play essential roles.

 

Matrices: Definition

Definition: A matrix is a rectangular array of numbers. A matrix with m rows and n columns is called an m    n matrix. 

  • The plural of matrix is matrices.
  •  A matrix with the same number of rows as columns is called square.
  • Two matrices are equal if they have the same number of rows and the same number of columns and the corresponding entries in every position are equal.

 

Matrices: Notation

Let m and n be positive integers and let…

 

Matrix Addition

Defintion: Let A = [aij] and B = [bij]  be m X n matrices. The sum of A and B, denoted by A + B, is the m X n matrix that has aij  + bij    as its (i,j)th element. In other words, A + B = [aij  + bij].

Example:


Note that matrices of different sizes can not be added.

 

Matrix Multiplication

Definition: Let A be an m X  k matrix and B be a k X n matrix. The product of A and B, denoted by AB, is the  m  X n matrix that has its (i,j)th element equal to the sum of the products of the corresponding elements from the ith row of A and the jth column of B. In other words, if AB = [cij] then cij = ai1b1j + ai2b2j + … + akjb2j.

Example:

The product of two matrices is undefined when the number of columns in the first matrix is not the same as the number of rows in the second.

The Product of A = [aij] and B = [bij]

Matrix Multiplication is not Commutative

 

Identity Matrix and Powers of Matrices

Definition: The identity matrix of order n is the n X n matrix In  = [δij], where δij  = 1 if i = j and δij  = 0 if i≠j.

 

Transposes of Matrices

Definition: Let A = [aij] be an m X n matrix. The transpose of A, denoted by At , is the n X m matrix obtained by interchanging the rows and columns of A.  If At = [bij], then  bij  = aji for i =1,2,…,n  and j = 1,2, …,m.

 

Zero-One Matrices

Definition: A matrix all of whose entries are either 0 or 1 is called a zero-one matrix. 

Algorithms operating on discrete structures represented by zero-one matrices are based on Boolean arithmetic defined by the following Boolean operations:

Definition: Let A = [aij]  and B = [bij] be an m × n zero-one matrices. 

  • The join of A and B is the zero-one matrix with (i,j)th  entry  aij ∨ bij. The join of A and B is denoted by A ∨ B. 
  • The meet of of A and B is the zero-one matrix with (i,j)th entry aij ∧ bij.  The meet of A and B is denoted  by A ∧ B. 

 

Joins and Meets of Zero-one matrices

 

Boolean Product of Zero-One Matrices

Definition: Let A = [aij]  be an m X k zero-one matrix and B = [bij] be a k X n zero-one matrix. The Boolean product of A and B, denoted by A ⊙ B, is the m X n zero-one matrix with(i,j)th entry

Solution: The Boolean product A ⊙ B is given by

Boolean Product of Zero-One Matrices

 

Boolean Powers of Zero-One Matrices

 

 

 

eof