# Explanation of matrix elements containing integers modulo a prime

From Cormen et all:

The elements of a matrix or vectors are numbers from a number system, such as the real numbers , the complex numbers , or integers modulo a prime .

What do they mean by integers modulo a prime ? I thought real numbers and complex numbers together make up all the elements of a matrix . Why did they put this additional one ?

-

You can actually form matrices with entries in any ring, although sometimes you won't have the same nice properties.

The ring of integers modulo a prime, sometimes denoted $\Bbb F_p$, is the ring where you perform modular arithmetic modulo $p$.

The reason to stick to a prime number (modular arithmetic can in fact be done modulo any natural number $N$) is that some nice properties are mantained, such as the possibility to find an inverse matrix whenever the determinant is not zero.

-
$\Bbb F_p$ is a field, so you can divide by any non-zero element. This is implied by the last sentence. For many of the algorithms of the course that is not important. –  Ross Millikan Aug 1 '12 at 13:46
@Andrea what does it mean when it is said that Let A, B be two square matrices over a ring R. I encountered it while reading the Strassen algorithm for multiplying square matrices here in wikipedia . In your answer also you mentioned about the ring and I am not clear on that part. –  Geek Aug 1 '12 at 14:21
It simply means that the entries of those matrices are in $R$. For instance, if $R=\Bbb Z$, then a "matrix over $R$" is simply a matrix with integer entries. –  Andrea Mori Aug 1 '12 at 14:29

Why did they put this additional one ?

They did not "put" and an additional one. These are all examples of different number system: that is, a set of number along with operations you can do.

I thought real numbers and complex numbers together make up all the elements of a matrix.

No we can have more than just real matrices and complex matrices. Check Andrea's answer.

Also, you may want to check the Wikipedia page for Real numbers, complex numbers, integers, rational numbers and integer modulo prime.

What do they mean by integers modulo a prime ?

Integers modulo prime, often denoted as $\mathbb{Z}/p \Bbb{Z}$ where $p$ is a prime. The form a finite field, but this won't be helpful for you now. For now, you can think of it as the numbers in the range $\{0, 1, 2, \ldots, p-1 \},$ and all the arithmetic ($+,-,\times,\div$) are performed modulo prime.

They have many applications e.g. in cryptography, coding theory. That's why we often need to consider matrices with such entries. On the other hand, engineering and physics deal with real & complex numbers, so we need matrices over the reals and complex numbers. Different domains different applications.

If you want to know more, you can read the Wikipage on modular arithmetic.

-

In the elementary case, matrices are defined to only contain complex numbers, of which real numbers are treated as a special case. In this sense, matrices only contain complex numbers (since every real number is complex).

However, there are more general notions of number than just complex numbers, so it makes sense to talk about matrices whose entries are drawn from those generalized numbers. Depending on your taste and the applications, it would be reasonable to let a "number system" be either a ring or a field, or maybe some other structure.

When we discuss matrices in general we want to have the most broad notion of number that still allows a rich theory. In this case the authors are choosing fields, of which the real numbers, the complex numbers, and the integers modulo a prime are all examples. One reason for choosing fields is that the determinant of a matrix over a field has familiar properties. For example, even in a general field, a matrix has an inverse iff its determinant is nonzero.

-