Lec 01 | Applied Optimization | Properties of Vectors and Matrices | IIT Kanpur

Hello, welcome to this module in this Massive Open Online Course. So let us start with the mathematical preliminaries that are required to understand the framework of optimization that is which form the basis of building the framework for optimization, the various tools and techniques for optimization. So we want to start with the mathematical preliminaries, the notation and so on that we are going to use frequently in our treatment of optimization in order to illustrate or in order to basically describe the various concepts of optimization. Now the first thing that we are going to use the mathematical construct that we are going to use is that of a vector as you must all be familiar a vector x bar which is denoted by a bar on the top of the quantity. So this basically is, so let us start with the concept of vectors and a vector is denoted by this quantities like this that is of the bar on the top. So this is basically a vector, so vector x bar is an n dimensional object which contains n components, these are the elements, so this is your, this is basically your n dimensional, this is your n dimensional vector contains n elements, this is an n dimensional vector and now if these elements x 1, x 2, x n these belong to the real field that is these are real numbers. Then we say that this is an n dimensional real vector that is x bar belongs to the set of n dimensional real vectors, alright. So this is the space of n dimensional real vectors and so what we have is if we consider x bar, now x bar is the column vector and therefore x bar transpose will similarly be a row vector. So it will be a 1 cross n, so this is basically your row vector x bar transpose, so this, so x bar is a column vector or basically n cross 1 has dimension n cross 1. Now x bar transpose, now this you can see this is a row vector which is of dimension 1 cross n that is 1 row and n columns and further x bar transpose x bar this is basically your x 1, x 2, x n the row vector times the product with the column vector x 1, x 2, x n and you can see this is basically equal to you can see this is x 1 square since these are real quantities x 2 square plus x n square which is also denoted by the norm square and in fact we will see this is a specific case of a norm this is the L 2 norm. So this is the square of the, so this indicates the L 2 norm of the vector where norm of x bar and this L 2 norm is the default, so this is the L 2 norm which is the default norm that we will use, so if there is a no, so the norm is not specified explicitly it will it indicates the L 2 norm and the L 2 norm of a vector is basically something that you are already very familiar with that is simply the length of the vector length of a vector in n dimensional space. So norm x bar is simply something that you are very must be most of you might be very familiar with that is square root of x 1 square plus x 2 square plus x n square which is basically the length of the vector. Now on the other hand now we have seen real vectors similarly if x 1 x 2 x n belong to the set of complex number, so now what we want to see is we want to see the notion of a complex vector. So a complex vector if x 1 x 2 x n are elements belong to C that is these are complex numbers then this implies that x bar the vector x bar belongs to the set of n dimensional complex vector C n that is this is n dimensional the space of n dimensional the space of n dimensional complex vectors. Now x bar Hermitian this is basically equal to x 1 conjugate x 2 conjugate x n conjugate that is first you take that is when you take the Hermitian of a vector or a matrix. In fact now here in this case you are taking the Hermitian of a vector the column vector becomes a row vector and you also in addition take the complex conjugate of each complex element. So that is basically your x bar Hermitian. So two steps one is you basically perform row vector plus the complex conjugate of the elements and x bar Hermitian into x bar is equal to x 1 x 2 conjugate x n conjugate times x 1 x 2 x n and this is equal to now the magnitude look at this is the x 1 conjugate into x 1 that is the magnitude x 1 square plus magnitude x 2 square plus so on up to magnitude x n square which is once again this is equal to the norm. In fact the L 2 norm of x bar square you can also write a 2 in the subscript to indicate that is L 2 norm. And therefore once again now you see that in this case the norm a complex vector x bar this is square root of magnitude x 1 square plus magnitude x 2 square plus magnitude x n square that is where we have replaced x i square with magnitude x i square. In fact this is a general definition that is magnitude x 1 square magnitude x 2 square magnitudes plus magnitude x n square and square root of that quantity this definition is general it works for both the real works for both real as well as complex way. So this in that sense this is a general definition for real numbers you can simply replace the magnitude square by the square of the element. So this is general definition for real and this is general definition that is applicable both for real and complex vectors. Now a special kind of a vector is obtained as following that is x tilde equals x bar divided by the norm of x bar that is you are taking the vector x bar and dividing it by the by its norm and that gives a unit norm vector. So this vector x tilde is basically unit norm vector because one you can show that the norm of x tilde is unity. So this vector x tilde has an interesting property x tilde is a unit norm. So x tilde is a unit norm vector and we can simply show that very easily as follows. In fact if you look at x tilde Hermitian x tilde that is x bar Hermitian divided by norm x bar times x bar divided by norm x bar is basically x bar Hermitian x bar that is norm x bar square divided by norm x bar square which is one. So this implies now x tilde Hermitian x tilde is nothing but norm x tilde square. So this implies norm x tilde square equals one this implies norm of x tilde equals one. So x tilde is basically a unit norm vector you can also say this is the unit norm vector in the direction of x bar. So if you think of this n dimensional vector x bar as representing a particular direction in n dimensional space the unit norm vector can think can be thought of as a unit vector basically pointing in that direction in n dimensional space that is the direction given by the vector x bar. So x bar and x tilde both are aligned except that x tilde this vector is a unit norm vector that is it has norm equal to unity. Let us take a simple example to understand this for instance let us consider the vector x bar let us consider this to be your x bar equals the all one vector that is n dimensional all one vector then we have norm of x bar equals square root of 1 square that is 1 plus 1 plus 1 n times that is equal to square root of n. In fact norm x bar square remember we are talking about l 2 norm x bar square equals n and in fact x tilde equals x bar divided by norm of x bar that is 1 over square root of n into the vector that is one vector of all one. So this is basically the corresponding unit norm this is the corresponding unit norm vector. So that is basically that completes a brief summary of the properties of the various aspects the various properties of vectors and most of you might already be familiar with many of these aspects but this presents a brief summary and will quickly refresh your memory and remind you of several of these aspects. So now let us look at matrices once again a brief review of various concepts in linear algebra and matrices. So let us consider an m cross n matrix A this implies A has m rows and n columns and you can represent A as the matrix a 1 1 a 1 2 so on up to a 1 n a 2 1 a 2 2 so on up to a 2 n and the mth row is a m 1 a m 2 so on up to a m n. So you can see there are m rows so there are m rows and there are n columns and note that this quantity for instance the i jth element a i j equals the element in ith row and the jth column this is the element in the ith row and the jth column and when the number of rows is equal to number of columns that is m equal to n then the matrix A becomes a square matrix. So if m equal to n then the matrix A is a square matrix that is when the number of rows is equal to the number of columns. Let us now look at an important concept of the row space and column space now to first understand this concept of a row space and column space of a matrix we have to understand what we mean by what we mean by the space and what we mean by the rank of a set of vectors. So let us start with this notion of rank so let us consider vectors w bar consider w bar 1 w bar 2 so on up to w bar m this is a set of this is a set of m vectors then now these vectors are linearly independent now this is an important concept so these are linearly independent so these are linearly independent if there do not exist c 1 c 2 so on up to c m not all 0 that is all of them cannot be 0 there do not exist c 1 c 2 c m not all 0 such that such that c 1 w bar 1 plus c 2 w bar 2 plus so on up to c m not all plus c m w bar m equals 0 that is there cannot be set of constant c 1 c 2 c m such that c 1 w bar 1 plus c 2 w bar 2 so on so forth up to c m w bar m equals 0 that this is known as a linear combination so there cannot be a linear combination of this vectors w bar 1 w bar 2 w bar m that equals 0 so this is basically a linear combination that is your weighing them by coefficients and adding them so this is basically a a linear combination so there cannot be a linear combination of vectors w bar 1 w bar 2 w bar m with coefficient c 1 c 2 c m or weight c 1 c 2 c m such that not all of them are 0 not with all of them not 0 such that not all of them are 0 such that this linear combination is 0 else they are linearly independent. Now, what is linearly independent linearly dependent else they are linearly dependent or let us look at this concept of linear dependence they are linearly dependent linearly dependent if there exist if there exist c 1 c 2 c m not all 0 with or such that such that c 1 w bar 1 plus c 2 w bar 2 plus c w bar m equals 0 so if there exist these weights c 1 c 2 c m such that not all of them are 0 and the linear combination of the vectors w bar 1 w bar 2 w bar m is 0 then these vectors w bar 1 w bar 2 w bar m are linearly dependent. So, this is basically a linear combination and these vectors are therefore, linearly dependent for instance let us take a very simple example to understand this consider the vectors w bar 1 equals 1 1 1 and w bar 2 equals minus 2 minus 2 minus 2 then you have w bar 1 plus you have 2 times you can easily see 2 times w bar 1 plus 1 times w bar 2 equals 0 implies w bar 1 plus w bar 1 comma w bar 2 are linearly dependent these are linearly dependent now on the other hand if consider another example w bar 1 equals 1 1 1 and w bar 2 equals well 1 2 3 you can quickly verify that you can check w bar 1 comma w bar 2 are linearly independent all right implies that there do not exist c 1 comma c 2 both not be independent of each other not 0 or not both 0 not both 0 that is 1 of them both 1 of them can be 0 such that c 1 w bar 1 plus c 2 bar 2 equals 0 they do not exist these weights such that the linear combination is. So, basically this is the concept of a linear dependence and linear independence of a set of vectors now if you go back and look at the matrix a now one can use this concept of linear independence to define the rank of the matrix a. So, let us go back and look at the matrix a as a set of remember it has n columns it is an m cross n matrix. So, you can either look at it as n columns or you can either look at it as you can either look at it as m rows. So, you have a 1 tilde let us say denotes the rows a 2 tilde and. So, these are basically your n columns and these are basically your m rows and now column rank of a equals the maximum number of linearly independent columns that is a bar 1 a bar 2 up to a bar n that is the maximum number of linearly maximum number of columns that you can choose from a such that the linear combination such that there does not exist any linear combination which is 0. So, maximum number of linearly independent columns of a now similarly the row rank of a equals the maximum number of linearly independent rows of a. So, this is the column rank of a and this is the row rank of a. So, you have this notion of row rank and you have the notion of column rank and one of the fundamental results in linear algebra or matrix theory is that the row rank of any matrix equals the column rank and this quantity is simply denoted by the rank of the row rank equals column rank which is simply denoted by the rank of the matrix a. So, we have the fundamental result and this should be available any standard text book or linear algebra that is the row rank equals the row rank of any matrix a equals column rank and this is therefore, simply denoted as the rank of matrix a and in addition this also satisfies the property that the rank of the matrix a is less than or equal to that is let me just write this again rank of the matrix a is less than or equal to the minimum of the number of columns comma rows of a. So, the rank of a is less than or equal to minimum of m comma n where m remember is number of rows and n equals number of columns. So, rank of any matrix is less than or equal to minimum of the number of rows and columns of the matrix and this is the fundamental property of the matrix this is one of the fundamental properties of the matrices which again some of you might already be familiar with. So, the rank so we have this notion of column rank which is the maximum number of linearly independent columns the row rank which is the maximum number of linearly independent rows and the fundamental theorem is that the row rank of the matrix of any matrix is equals is equal to its column rank which is simply denoted by the rank of the matrix a and further this rank has to be less than or equal to the minimum of the number of rows and columns of the matrix. So, we have covered some of the mathematical preliminaries required to develop the various tools and techniques for optimization we will continue this discussion in the subsequent modules. Thank you very much.