Payman Biukaghazadeh (Amirkabir University of Technology, Iran)
DOI: 10.4018/978-1-4666-2661-4.ch002
OnDemand PDF Download:
No Current Special Offers


Matrices are one of the most important tools of representing graphs. Various types of matrices are used for this purpose. This chapter teaches about the definitions and the standard notations of the matrices. Then, some kinds of the matrices such as Adjacency, Incidence, Cycle and Cut-set are introduced. Some discussions will be made on the applications of these matrices. Advanced topics on matrices will be the final part.
Chapter Preview


  • Matrix: An arrangement of the mathematical elements in a rectangular form, which could be summed or multiplied with similar arrangements having the same number of rows and columns (Merriam-Webster online Dictionary).

The maximal number of linearly independent columns of a matrix A is called the column rank of that matrix. Similarly, the maximal number of linearly independent rows of a matrix A is called the row rank of that matrix.

  • Matrix Rank: For a given matrix Am×n the rank is the min (column rank, row rank). Rank of a matrix is denoted by rk (A) or rank (A). The Min (m, n) is the maximum value for rank of a m × n matrix. A matrix is called fully rank, if it has the largest possible rank; else, it is called a rank deficient matrix. Example 1 shows a matrix and its rank computation.

Example 1: Consider the matrix A. It could be seen that the elements of the second column is twice the first column is and the sum of the first and second columns result in the fourth column. So, column rank is 2. The row rank of this matrix is 2. Then, matrix rank is 2.

  • o

    The properties of the matrix rank are as follow: (Godsil & Royle, 2000):

    • Only a zero matrix has a rank of zero.

    • Rank (A) ≤ min (m, n).

    • If 978-1-4666-2661-4.ch002.m02 with the rank of n and 978-1-4666-2661-4.ch002.m03

    • If 978-1-4666-2661-4.ch002.m04 and 978-1-4666-2661-4.ch002.m05 then: Rank (A) + Rank (B) – nRank (AB).

    • Rank978-1-4666-2661-4.ch002.m06

      • Graph rank: The rank of a graph G is defined as r (G) = nc. In this definition, the number of vertices of G is denoted by n and the number of connected components is shown by c (Biggs, 1993). Obviously, for a connected graph, its rank is equal to the number of vertices.

Complete Chapter List

Search this Book: