# Chapter 4

## 4.1 Arrays and Matrices

In the programs we have written so far, we have concerned ourselves mostly with integers, floating point (real numbers) and characters. These data types are referred to as scalar or base data types. Many languages provide support for compound data structures, which are organized groups of such basic data types. A very commonly used class of such data structures in programming is arrays. Arrays can be one- or multi-dimensional. A one-dimensional array is essentially a list of numbers or values (of a single type, i.e. all integers or all floating points) whose individual elements can each be accessed by means of a single index. In more technical terms, a onedimensional array is an ordered sequence of identical objects. Mathematically speaking, they can be associated with vectors in linear algebra. The ordering in a vector or a one-dimensional index is determined by a single index. Let us first see an example of how an array may be formed in Octave.

``octave:1> for n=1:5``
``> a(n)=n^2;``
``> endfor octave:2``
``> a``
``a=``
``    1 4 9 16 25``
``octave:3> a(3)``
``ans = 9``

As you see in the above example, a, is a list of values that are indexed by an array index, n. The way arrays are stored in memory follow a simple logic. As we have briefly mentioned before, each variable has an address in memory. Let us see this by means of a simple python snippet:

``>>> a=5``
``>>> id(a)``
``38002936``
``>>> hex(id(a))``
``'0x243e0f8'``
``>>> b=4.3``
``>>> hex(id(b))``
``'0x244f6d0'``
``>>> a=b``
``>>> hex(id(a))``
``'0x244f6d0'``

Here id(a) and id(b) refer to the numerical address of either variable. As a side note, notice that the address of a and b are the same after we assign b to a since they are referring to the same object.

The memory storage of an array is, instead, by means of the allocation of a memory block. If we are creating an array of five 8-bit integers, a memory block of 8 × 5 = 40 bits (or simply 5 bytes) must be set aside (allocated). This chunk of memory may be allocated in a contiguous or fragmented manner. Either way, the operation of accessing a and a actually means going to their location in the memory and retrieving them. If the array is allocated in a contiguous manner, sequential access of its elements will be more efficient. In Python, memory allocation is fragmented.

``>>> a=(1,2,3)``
``>>> hex(id(a))``
``'0x243e158'``
``>>> hex(id(a))``
``'0x243e140'``
``>>> hex(id(a))``
``'0x243e128'``

Multi-dimensional arrays can have multiple indices. Matrices are a special class of multidimensional arrays, which only carry two indices. They essentially have the same meaning as matrices in math. All computer languages have a different way of handling arrays and matrices. Some examples from Octave involving arrays are as follows:

``octave:1> v=[1 2 3 4]``
``v=``
``    1 2 3 4``
``octave:2> v'``
``ans =``
``    1``
``    2``
``    3``
``    4``
``octave:3> size(v)``
``ans =``
``    1 4``
``octave:4> v=1:5``
``v=``
``    1 2 3 4 5``
``octave:5> v2=6:-2:-6``
``v2 =``
``    6 4 2 0 -2 -4 -6``
``octave:6> M=[1 2;3 4]``
``M=``
``    1 2``
``    3 4``
``octave:7> M1=rand(3,4)``
``M1 =``
``    0.389566 0.085961 0.357163 0.372460 ``
``    0.533944 0.952454 0.355170 0.886790 ``
``    0.330111 0.059911 0.397116 0.073798 ``
``octave:8> v1=rand(3,1)``
``v1 =``
``    0.35705``
``    0.47673``
``    0.86916``
``octave:9> M1*v1``
``error: operator *: nonconformant arguments (op1 is 3x4, op2 is 3x1)``
``octave:9> v1=rand(4,1)``
``v1 =``
``    0.264192``
``    0.073931``
``    0.028511``
``    0.192000``
``octave:10> M1*v1``
``ans =``
``    0.19097 0.39187 0.11713``

In the above `Octave` snippet, we first present the simplest way of forming an array, that is to say, placing the elements one after the other. We then take the transpose of the array using `'` and find out its size using `size`. Note that in Octave, the size of arrays are given in such a way as to present first the number of rows and then the number of columns. For example, the `[1 2 3 4]` would be a 1 × 4 array. Then we utilize a very common way of forming arrays of number that involve an interval and an increment. The expression `1:5` immediately yields the numbers between 1 and 5 (including the endpoints) in increments of 1. While the default increment is 1, we can use any increment that makes sense, including nonintegers and negative numbers. An example can be seen above where `6:-2:-6` produces a backwards array of numbers from 6 to -6 in steps of -2.

Later, we form a simple 2 × 2 matrix by means of typing out the elements. Note that after we enter the first line, we use the separator `;` to indicate that we are about to enter the next line. Note also that the elements of both arrays and matrices are delimited by "square braces" ([ ]). In Octave there are many specialized functions for dealing with arrays. One such function is `rand(n,m)` which produces an n × m matrix of random numbers from a continuous uniform distribution of numbers between `0` and `1`. In the above example `rand(3,4)` produces a 3 × 4 matrix of such numbers. Finally, we try a matrix-vector multiply. We first form a random 3 × 1 array and try to multiply it with our 3 × 4 array. As this multiplication would not be possible in math, so it is not in Octave. Instead, when we try to multiply a 3 × 1 array with a 4 × 1 matrix, the operation is executed in line with the regular linear algebraic expression where `M` is a matrix and `v` is an array.

There are many more matrix and array operations in Octave, some of which we present here to introduce some ideas that are similar in other languages as well. Please read the below operations and their analysis carefully.

``octave:1> M=eye(3)``
``M=``
``   1 0 0``
``   0 1 0``
``   0 0 1``
``octave:2> M=ones(3)``
``M=``
``   1 1 1``
``   1 1 1``
``   1 1 1``
``octave:3> M=zeros(3)``
``M=``
``   0 0 0``
``   0 0 0``
``   0 0 0``
``octave:4> M=[1 2 3;``
``> 4 5 6;``
``> 7 8 9]``
``M=``
``   1 2 3``
``   4 5 6``
``   7 8 9``
``octave:5> v=[1;2;3]``
``v=``
``   1``
``   2``
``   3``
``octave:6> M*v``
``ans =``
``   14``
``   32``
``   50``
``octave:7> v*M``
``error: operator *: nonconformant arguments (op1 is 3x1, op2 is 3x3)``
``error: evaluating binary operator `*' near line 7, column 2``
``octave:8> v'*M``
``ans =``
``   30 36 42``
``octave:9> M=rand(3)``
``M=``
``   0.687971 0.207907 0.359514``
``   0.810225 0.967850 0.541394``
``   0.716802 0.802503 0.063585``
``octave:10> M=3*M``
``M=``
``   2.06391 0.62372 1.07854``
``   2.43067 2.90355 1.62418``
``   2.15040 2.40751 0.19075``
``octave:11> M=[1 2 3;1 2 3;1 2 3]``
``M=``
``   1 2 3``
``   1 2 3``
``   1 2 3``
``octave:12> M.^2``
``ans =``
``   1 4 9``
``   1 4 9``
``   1 4 9``
``octave:13> N=[2 3 4;4 5 6;6 7 8];``
``octave:14> M.*N``
``ans =``
``   2  6 12``
``   4 10 18``
``   6 14 24``

You might have noticed in the above example that there are several specialized functions and operations related to matrices.

• `eye(n)` makes an n × n identity matrix.
• `ones(n)` and `zeros(n)` make n × n matrices whose elements are all ones or zeros respectively.
• `diag([<vector>],n)` makes a matrix whose nth diagonal is <vector>. The size of the matrix is adjusted according to the length of <vector>. A negative n designates a diagonal below the main diagonal.
• `rand(n)` makes an n × n matrix of uniformly distributed random numbers.
• In addition to these speacialized function, you can also type the contents of a matrix line-by-line as seen on the fourth line in the above example. This again has the same disadvantage as creating files with cat, namely you cannot go back using Backspace.
• Addition, subtraction and multiplication are performed with using the usual symbols. This is a nice feature of Octave because in most other programming languages performing the same operation for different data types would require different symbols or functions.
• Multiplication of matrices with vectors or other matrices are only possible if the dimensions are correct. For instance, you can multiply a 3 × 4 matrix by a 4 × 2 matrix, but not not by a 2 × 4 matrix.
• The symbol `'` stands for the transpose of a matrix.
• Matrices may also be multiplied by real or complex numbers as seen on the 10th line.
• On the twelfth and fourteenth lines, we see an interesting operation done on matrices, which is the element-by-element multiplication. The `.` after the matrices causes the matrix to be raised to the power two or muliplies by another matrix element-by-element. Note that this is NOT the same operation as matrix multiplication.

### Lists and Tuples

In python, there are two objects that can be used to define and manipulate arrays: lists and tuples. Let us see the difference by a simple example:

``>>> a=(9,3,8,5,9,6)``
``>>> a``
``9``
``>>> a``
``3``
``>>> a``
``9``
``>>> len(a)``
``6``
``>>> a(3)=7``
``   File "<stdin>", line 1``
``SyntaxError: can't assign to function call``
``>>> type(a)``
``<type 'tuple'>``
``>>> b=[9,3,8,5,9,6]``
``>>> b``
``9``
``>>> b``
``3``
``>>> b``
``9``
``>>> len(b)``
``6``
``>>> b=7``
``>>> b``
``[9, 3, 8, 7, 9, 6]``
``>>> type(b)``
``<type 'list'>``

When the array is defined using regular parenthesis as in the definition of a in the above example, it is called a tuple. The length of the list can be obtained using the built-in function len and the elements can be accessed by their corresponding index with a[n]. NOTE that the indices in Python start from 0. If you now attempt to change any of the elements bu means of reassigning it to another value, you will receive and error message. This operation is not permitted because once a tuple is created, its elements and its size cannot be changed. Tuples are thus said to be immutable.

A list, on the other hand, is created using square braces. Its length and individual elements can be accessed in much the same way as a tuple. The only difference is that elements of a list can be modified. As such, lists are mutable objects. Let us see some operations that can be performed using lists.

``>>> a=[9, 3, 8, 7, 9, 6]``
``>>> a[3:]``
``[7, 9, 6]``
``>>> a.append(4)``
``>>> a``
``[9, 3, 8, 7, 9, 6, 4]``
``>>> a.append(12)``
``>>> a``
``[9, 3, 8, 7, 9, 6, 4, 12]``
``>>> a.remove(12)``
``>>> a``
``[9, 3, 8, 7, 9, 6, 4]``
``>>> a.remove(9)``
``>>> a``
``[3, 8, 7, 9, 6, 4]``
``>>> a.remove(9)``
``>>> a``
``[3, 8, 7, 6, 4]``
``>>> a.reverse()``
``>>> a``
``[4, 6, 7, 8, 3]``
``>>> b=[6,2,8,9,1]``
``>>> a+b``
``[4, 6, 7, 8, 3, 6, 2, 8, 9, 1]``
``>>> zip(a,b)``
``[(4, 6), (6, 2), (7, 8), (8, 9), (3, 1)]``
``>>> [x+y for x,y in zip(a,b)]``
``[10, 8, 15, 17, 4]``
``>>> c=[x+y for x,y in zip(a,b)]``
``>>> c``
``[10, 8, 15, 17, 4]``
``>>> d=[x**2 for x in range(6)]``
``>>> d``
``[0, 1, 4, 9, 16, 25]``

There is a lot of material to be covered in the above snippet. Let us go through it line-by-line.

• a[3:] : Slicing -- Show elements that have indices greater than or equal to 3.
• a.append(4) : The format object.method(arguments) is a common construct in Python. This means the following: we have an object, say a, and it has a certain number of functions that can be applied to it called methods. In this case, append is a method that can be applied to lists and adds an element to the end of an already created list. If you try to append an element to a tuple, instead, you will get an error message since tuples cannot be modified once created, as discussed above.
• a.remove(12) : remove is another method that removes an element from an array, given the element itself. A similar method, pop removes the element, given its index. Try it out!
• a.reverse() : This is a method that does not take any arguments since it applied to the whole array. It reverses the elements.
• a+b : Two lists cannot be added in the mathematical way with the addition symbol. It is a simple concatenation.
• zip(a,b) : zip is a function that creates ordered pairs from two arrays, a and b. Mathematical addition of two arrays can be achieved by means of the zip command and using list comprehension as explained in the following paragraph.

The last two commands in the above code snippet,

``>>> c=[x+y for x,y in zip(a,b)]``
``>>> c``
``[10, 8, 15, 17, 4]``
``>>> d=[x**2 for x in range(6)]``
``>>> d``
``[0, 1, 4, 9, 16, 25]``

are shortcuts for loops and are called instances of list comprehension. Let us first look at the addition example. We can achieve the same task using a loop as follows:

``a=[1,2,3,4,5,6]``
``b=[6,7,3,9,1,5]``
``c=[]``
``L=len(a)``

``for n in range (L):``
``      c.append(a[n]+b[n])``

``print c``

The shortcut just creates the ordered pairs and adds them, assigning the result to a new array, a, all at once. The second example, creates an array of numbers that are squares of indices ranging from 0 to 5. The loop representation would be:

``d=[];``
``for n in range(6):``
``      d.append(n**2)``

``print d``

Matrices in Python are seen as lists of lists, as illustrated by the following examples:

``>>> M=[[1,2,3],[5,6,7],[2,1,4]]``
``>>> M``
``[[1, 2, 3], [5, 6, 7], [2, 1, 4]]``
``>>> M``
``2``
``>>> M``
``7``
``>>> M[:]``
``[2, 1, 4]``
``>>> M``
``[5, 6, 7]``
``>>> b=M``

In python, there is a special package for handling arrays and matrices, called NumPy. NumPy has many built-in operations including matrix addition, subtraction, multiplication, scalar and cross product of arrays. Let us practice some of these. Remember that in order to pull up python in your terminal, you just have to type python.

``>>> import numpy``
``>>> a=numpy.array([1,2,3,4])``
``>>> a+1``
``array([2, 3, 4, 5])``
``>>> b=numpy.array([-2,-4,-6,-8])``
``>>> a+b``
``array([-1, -2, -3, -4])``
``>>> c=a+b``
``>>> c``
``array([-1, -2, -3, -4])``
``>>> M=numpy.ones((3,4))``
``>>> M``
``array([[ 1., 1., 1., 1.],``
``          [ 1., 1., 1., 1.],``
``          [ 1., 1., 1., 1.]])``
``>>> v=numpy.arange(5)``
``>>> v``
``array([0, 1, 2, 3, 4])``
``>>> M = numpy.array([[ 5, 1 ,3], [ 1, 1 ,1], [ 1, 2 ,1]])``
``>>> M``
``array([[5, 1, 3],``
``          [1, 1, 1],``
``          [1, 2, 1]])``
``>>> b=numpy.array([,  ,])``
``>>> M*b``
``array([[25, 5, 15],``
``          [ 1, 1, 1],``
``          [ 3, 6, 3]])``
``>>> b*M``
``array([[25, 5, 15],``
``          [ 1, 1, 1],``
``          [ 3, 6, 3]])``
``>>> numpy.dot(M,b)``
``array([,``
``          [ 9],``
``          ])``
``>>> numpy.dot(b,M)``
``Traceback (most recent call last):``
``   File "<stdin>", line 1, in <module>``
``ValueError: objects are not aligned``
``>>> M1=numpy.random.rand(3,3)``
``>>> M2=numpy.random.rand(3,3)``
``>>> M1``
``array([[ 0.64027404, 0.1813327 , 0.31168824],``
``          [ 0.39307289, 0.02503093, 0.74346459],``
``          [ 0.43367454, 0.29880343, 0.7940594 ]])``
``>>> M2``
``array([[ 0.66172037, 0.13787459, 0.77113553],``
``           [ 0.38078167, 0.26602765, 0.15919714],``
``           [ 0.984256 , 0.89497199, 0.06530093]])``
``>>> M3=M1+M2``
``>>> M3``
``array([[ 1.30199441, 0.3192073 , 1.08282378],``
``           [ 0.77385457, 0.29105858, 0.90266173],``
``           [ 1.41793055, 1.19377542, 0.85936032]])``

## 4.2 Associative arrays

In the above exercises, we considered arrays whose indices were numerical. However, in reality, great flexibility can be achieved if arrays are allowed to have nonnumerical indices. A good example is the record of a student that the university may hold. This record probably contains the student's name, her/his student ID, major and CGPA. Consider the following method for creating an array to hold this information. Notice that some of the information is in the form of strings (name, major) while the rest is numeric (ID, CGPA). You will remember that with regular arrays, it is not possible to mix data types in this way.

``>>> a={'Name':'XXX YYY','ID':'12345','Major':'Physics','CGPA':'3.45'}``
``>>> a['Name']``
``'XXX YYY'``
``>>> print a['ID']``
``12345``
``>>> print a['Major']``
``Physics``
``>>> a``
``Traceback (most recent call last):``
``   File "<stdin>", line 1, in <module>``
``KeyError: 0``

In the above expression, instead of numerical values, the elements are indexed with meaningful expressions and the corresponding elements are the values corresponding to these properties. Such arrays take several names in different computer languages. Associated arrays, structures, maps and dictionaries. You can access the value of each entry simply by using the regular array access syntax but with the index keyword (such as Name, ID etc). Indeed, if you use a numerical index in an array defined as a dictionary, you will get an error.

Notice in the below example notice the similarity between changing an already existent element (updating the CPGA at the beginning of the year) and adding a new element to an array (the student's year).

``>>> print a``
``'Major': 'Physics', 'CGPA': '3.45', 'Name': 'XXX YYY', 'ID': '12345'``
``>>> a['CGPA']=3.57``
``>>> a['Year']='Junior'``
``>>> print a``
``'Year': 'Junior', 'Major': 'Physics', 'CGPA': 3.57, 'Name': 'XXX YYY', 'ID': '12345'``

Notice also the fact that the order of the elements is scrambled; however, this is not important since the indices are not numerical and do not follow any order.

A university or a department has several thousands of students whose records need to be kept. In order to organize a collection of such records, one may also think of creating an array of such dictionaries. See the example below.

``>>> a``
``{'Year': 'Junior', 'Major': 'Physics', 'CGPA': 3.57, 'Name': 'XXX YYY', 'ID': '12345'}``
``>>> b={'Name':'ZZZ WWW','ID':'54321','Major':'Math','CGPA':'2.67','Year':'Senior'}``
``>>> students=[a,b]``
``>>> students``
``[{'Year': 'Junior', 'Major': 'Physics', 'CGPA': 3.57, 'Name': 'XXX YYY', 'ID': '12345'},``
``{'Year': 'Senior', 'Major': 'Math', 'CGPA': '2.67', 'Name': 'ZZZ WWW', 'ID': '54321'}]``
``>>> students``
``{'Year': 'Junior', 'Major': 'Physics', 'CGPA': 3.57, 'Name': 'XXX YYY', 'ID': '12345'}``
``>>> students['Name']``
``'XXX YYY'``
``>>> print students['Major']``
``Math``

In this example, once there are more than one student records, you may form an array from them. Accessing each student's record is as simple as calling an element of a numerically indexed array.

If you would like to create dictionaries that have fields with subfields, i.e. say you want to separately store each student's first and last names, you can also use the concept called nesting.

``>>> c={'Name':{'First':'XXX','Last':'DDD'},'Major':'Political Science', 'CGPA':{'Freshman':'1.65','Sophomore':'2.00', 'Junior':'2.25','Senior':'Ongoing'}}``
``>>> print c``
``{'Major': 'Political Science', 'CGPA': {'Freshman': '1.65', 'Senior': 'Ongoing', 'Junior': '2.25', 'Sophomore': '2.00'}, 'Name': {'Last': 'DDD', 'First': 'XXX'}}``
``>>> print c['CGPA']['Freshman']``
``1.65``
``>>> print c['Name']['First']``
``XXX``

The type of the dictionary defined in the manner discovered above is different from a regular array. Remember that the function type can be used in python to find out the data type of the variable at hand.

``>>> z``
``[1, 2, 3, 4, 6]``
``>>> type(z)``
``<type 'list'>``
``>>> a``
``{'Year': 'Junior', 'Major': 'Physics', 'CGPA': 3.57, 'Name': 'XXX YYY', 'ID': '12345'}``
``>>> type(a)``
``<type 'dict'>``

## 4.3 Functions

While writing code, we often find ourselves repeating the some set of actions many times. For example, you may want to find the greatest common denominator of two numbers once and a different pair numbers later. Of course, it would be inconceivable to type all the commands necessary over and over again for different pairs of numbers. Instead, what we resort to are functions or subroutines that we can call every time we need to repeat the same operation. A function in the computational context is very similar to a function in math. A mathematical function can be described (incompletely) as a map from one space to another. In simpler terms it takes one or more numbers, applies an operation on them and produces another number as a result:

y = f (x) : x → y

In this case, x may be regarded as the input of this function while y as the output. Similarly, a function in a computer program takes in one or more inputs and returns one or more outputs. Outputs are also referred to as return values. Once you write a function, you can then call it with various input values. In order to illustrate this better, let us now write an example in Python and Octave. For this, we start emacs with the file max_elt.m which is going to be function that returns the the maximum element of a matrix. Inside this function, let us type the following:

``function m_elt=max_elt(M)``
``    m_elt=max(max(M));``
``endfunction``

Let us look at several aspects about this simple one-liner (i.e. a complete unit of code that achieves a task in a single line.).

• Each function in Octave starts with the keyword `function` and ends with the matching keyword `endfunction`.
• The input/output structure of the function is declared in the first line. The statement `m_elt=max_elt(M)` means that this function is to take in as input a matrix, M, and returns a number m_elt.
• The special function in Octave that finds the maximum of an array max is used twice, `max(max(M))`. The first instance `max(M)` finds the maximum of each column, and the second, `max(max(M))` finds the maximum among the maxima of the columns. In order to see how this works, you can try it out in an Octave window.

Let us try this function out with different matrices. In order to do this, go to your terminal and type octave. When the octave prompt appears, type the following and observe the outcomes:

``octave:1> M``
``error: 'M' undefined near line 1 column 1``
``octave:1> m_elt``
``error: 'm_elt' undefined near line 1 column 1``
``octave:1> M=[1 2;3 4]``
``M=``
``     1 2``
``     3 4``
``octave:2> m_elt=max_elt(M)``
``m_elt = 4``
``octave:3> M1=rand(2,3)``
``M1 =``
``     0.503388 0.773910 0.175344``
``     0.743223 0.084745 0.785388``
``octave:4> m=max_elt(M1)``
``m = 0.78539``

Once again, let us analyze some important points about the above session:

• In Octave, the name of the function must match the name of the file where the function is stored. This means that if the function is called max_elt then the file must be called max_elt.m.
• Octave will only recognize those functions that are written under the same folder as the current working directory.
• Although the function is written and saved in the current directory, the variables within the function M and m_elt are not recognized outside the function in the external session until we defined them explicitly. This is due to the fact that variables inside a function are local.
• While calling the function, you can use the same names for the input/output variables (the first instance above) or you can different names.

Now, let us go over the same set of operations in Python. Let us open a file called function_max_elt.py and type the following.

``#!/usr/bin/python``
``import numpy``

``def max_elt(M):``
``      "Takes in a matrix and returns its maximum value."``
``      m_elt=numpy.amax(M1)``
``      return m_elt``

``M1=numpy.random.rand(3,3)``
``a=max_elt(M1)``
``print "This is the matrix:\n"``
``print M1``
``print "This is the maximum element.\n"``
``print a``

When you go to your terminal and type (after making this file an executable like we have done several times already) function_max_elt.py, you will see something like the following:

``This is the matrix:``
``[[ 0.46132011 0.67603979 0.0212634 ]``
`` [ 0.11571912 0.45498968 0.18228824]``
`` [ 0.01342137 0.49029071 0.26516198]]``
``This is the maximum element.``
``0.676039788505 ``