{ "cells": [ { "cell_type": "markdown", "metadata": { "tags": [ "s1", "content", "l1" ] }, "source": [ "# Linear Algebra - Advanced\n", "\n", "## Trace and Determinant \n", "\n", "### Trace\n", "\n", "In linear algebra, the trace of an n-by-n square matrix A is defined to be the sum of the elements on the main diagonal (the diagonal from the upper left to the lower right) of A. \n", "\n", "\n", "\n", "**The sum of Eigen Values corresponds to the trace of the matrix.**\n", "\n", "### Determinant \n", "\n", "In Linear Algebra, determinant of a matrix is a special number that can be calculated from a square matrix. \n", "\n", "For a 2×2 matrix:\n", "\n", " A=$\\left[\\begin{array}{cc}a & b \\\\c & d\\\\\\end{array}\\right]$\n", " \n", " The determinant is found by,\n", " \n", " **|A| = (a \\* d) − (b \\* c)**\n", " \n", "For a 3x3 matrix:\n", "\n", "\n", "\n", " A=$\\left[\\begin{array}{cc}a & b & c \\\\d & e &f\\\\ g &h&i\\\\\\end{array}\\right]$\n", " The determinant is found by,\n", " **|A| = a((e \\* i) − (f \\* h)) − b((d \\* i) − (f \\* g)) + c((d \\* h) − (e \\* g))**\n", " \n", "**Determinant of a matrix can also be found by product of its eigenvalues.**\n", "\n", "## Exercise \n", "\n", "Find determinent of a matrix using \"numpy.linalg.det\" in python and store its value in variable called d.\n", "\n" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": true, "tags": [ "s1", "ce", "l1" ] }, "outputs": [], "source": [ "a = np.array([[5, 4], [1, 2]])" ] }, { "cell_type": "markdown", "metadata": { "tags": [ "s1", "l1", "hint" ] }, "source": [ "### Hint\n", "\n", "Use the np.linalg.det function in numpy module and pass the array a as an argument to find out the determinant of a" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "tags": [ "s1", "l1", "ans" ] }, "outputs": [ { "data": { "text/plain": [ "6.0" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "b=np.linalg.det(a)\n", "b" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "tags": [ "s1", "hid", "l1" ] }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "continue\n" ] } ], "source": [ "ref_tmp_var = False\n", "\n", "try:\n", " import numpy as np\n", "\n", " if np.all(b == 6.0) :\n", " ref_assert_var = True\n", " ref_tmp_var = True\n", " else:\n", " ref_assert_var = False\n", " print('Please follow the instructions given and use the same variables provided in the instructions. ')\n", "\n", "except Exception:\n", " print('Please follow the instructions given and use the same variables provided in the instructions. ')\n", "\n", "assert ref_tmp_var" ] }, { "cell_type": "markdown", "metadata": { "tags": [ "l2", "content", "s2" ] }, "source": [ "\n", "\n", "## Matrix Decomposition \n", "\n", "Decomposition means breaking of a large entity into smaller ones. Similarly, matrix decompositon or matrix factorization means decomposing or factorizing a large matrix into smaller ones. The usefullness of decompostion is that it helps us in learning about some special properties of the matrix which we couldn't have done if we hadn't decomposed it. Here we will talk about decomposition of a matrix into **Eigen Vectors and Eigen Values**\n", "\n", "\n", "## Eigen Values and Eigen Vectors\n", "\n", "In practical applications, many problems are presented in the form of Eigenvalue problem:\n", "

\n", "**A·v = λ·v**\n", " \n", "In this equation A is an n-by-n matrix, v is a non-zero n-by-1 vector and λ is a scalar (which may be either real or complex). Any value of λ for which this equation has a solution is known as an eigenvalue of the matrix A. It is sometimes also called the characteristic value. The vector, v, which corresponds to this value is called an eigenvector. The eigenvalue problem can be rewritten as:\n", "

\n", "**(A·v) - (λ·v) = 0**\n", "
\n", "**(A·v) - (λ·I·v) = 0**\n", "
\n", "**(A - (λ·I))·v = 0**\n", "
\n", "If v is non-zero, this equation will only have a solution if \n", "\n", "**|A - (λ·I)| = 0**\n", " \n", "This equation is called the characteristic equation of A, and is an nth order polynomial in λ with n roots.\n", "\n", "**|A - (λ·I)| = (λ1-λ)(λ2-λ)…(λn-λ)**\n", "

\n", "These roots are called the eigenvalues of A. For each eigenvalue there will be an eigenvector for which the eigenvalue equation is true. In python we can find eigen values and eigen vectors using \"linalg\" package from scipy. \n", "\n", "


\n", "## Eigen Decomposition\n", "\n", "As seen in the topics above, Eigen Decomposition is the factorization of a matrix into a canonical form, whereby the matrix is represented in terms of its eigenvalues and eigenvectors.\n", "\n", "Lets see an example:\n", "\n", "\n", "\n", "Let's see the eigendecomposition for the matrix:\n", "\n", "A=$\\left[ \\begin{array}{cccc}\n", "1 & 1 \\\\\n", "0 & 3 \\\\ \\end{array} \\right]$\n", "\n", "From above we can find determinant of the matrix as:\n", "\n", "det$\\left( \\begin{array}{cccc}\n", "1-\\lambda & 0 \\\\\n", "1 & 3-\\lambda \\\\ \\end{array} \\right)$\n", "\n", "**(1−λ)(3−λ)=0**\n", "\n", "\n", "we get directly **λ1 =1 and λ2=3**. The above expression is usually referred as the **characteristic polynomial or characteristic equation of a matrix**. \n", "\n", "Putting λ1 in the equation, we get:\n", "\n", "$\\left[\\begin{array}{cc}1 & 0\\\\1 & 3\\\\\\end{array}\\right]\\left[\\begin{array}{c}v_{11}\\\\v_{12}\\\\\\end{array}\\right]$ = 1 $\\left[\\begin{array}{c}v_{11}\\\\v_{12}\\\\\\end{array}\\right]$\n", "\n", "\n", "from which we get \n", "\n", "**v11=−2v12**. \n", "\n", "That is, any vector **v1=[v11,v12] **where **v11=−2v12** is an eigenvector of A with eigenvalue 1. Putting λ2 into equation, we get:\n", "\n", "$\\left[\\begin{array}{cc}1 & 0\\\\1 & 3\\\\\\end{array}\\right]\\left[\\begin{array}{c}v_{21}\\\\v_{22}\\\\\\end{array}\\right]= 3 \\left[\\begin{array}{c}v_{21}\\\\v_{22}\\\\\\end{array}\\right]$\n", "\n", "from which we get v_21 = 0 and v_22 ∈R . That is, any vector v_2 = [v_21, v_22] where v_21 = 0 is an eigenvector of A with eigenvalue 3.\n", "\n", "### Use of Eigen Decompositon\n", "\n", "From our previous example, we can use eigen values and eigen vectors, join them in a single matrix equation.\n", "\n", " A$\\left[\\mathbf{v_1 v_2}\\right]$ = $\\left[\\begin{array}{cc}1 & 0\\\\1 & 3\\\\\\end{array}\\right]$\n", " $\\left[\\begin{array}{cc}v_{11} & v_{21}\\\\\n", " v_{12} & v_{22}\\\\\\end{array}\\right]$ = \n", " $\\left[\\begin{array}{cc}v_{11} & v_{21}\\\\v_{12} & v_{22}\\\\\\end{array}\\right]$\n", " $\\left[\\begin{array}{cc}\\lambda_1 & 0\\\\0 & \\lambda_2\\\\\\end{array}\\right]$ =\n", " $\\left[\\mathbf{v_1 v_2}\\right]$\n", " $\\left[\\begin{array}{cc}\\lambda_1 & 0\\\\0 & \\lambda_2\\\\\\end{array}\\right]$\n", " \n", " If we replace the value,\n", " \n", " λ=$\\left[\\begin{array}{cc}\\lambda_1 & 0\\\\0 & \\lambda_2\\\\\\end{array}\\right]$\n", " \n", " V = $\\left[\\mathbf{v_1 v_2}\\right]$\n", " \n", " it becomes,\n", "\n", " **AV=VΛ**\n", " \n", " **A=VΛV−1**\n", " \n", "Eigendecomposition decomposes a matrix A into a multiplication of a matrix of **eigenvectors V** and a **diagonal matrix of eigenvalues Λ** as **A=VΛV−1**\n", "\n", "### Benefits of Eigen Decomposition \n", "\n", "If all eigenvalues are positive, then the matrix is positive definite. If all eigenvalues are positive or zero-valued, then the matrix is positive semi-definite. Similar is the case negative definite and negative semi-definite.\n", "There are benefits to knowing that a matrix is positive definite, positive semi-definite, negative definite and negative semi-definite. Many useful facts can be gather using this -\n", "\n", "* A matrix is singular if and only if any of the eigenvalues is zero\n", "* It can be used to optimize quadratic expressions of the form **f(x)=xTAx subject to ||x||2=1** \n", "* The determinant of a matrix is equal to the sum of all eigenvalues of a matrix\n", "\n", "Eigen decomposition can be performed on a matrix using the 'linalg.eig' function from linear algebra sub-module from scipy library. The linalg.eig function returns two outputs - the eigen values of the input matrix and the right eigen vectors of the matrix. Hence, the function output is generally captured by using two variables, For e.g., B,C = linalg.eig(A). In this way, the eigen values of Matrix A are assigned to variable B and right eigen vectors are assigned to variable C.\n", "\n", "### Exercise: \n", "\n", "Given matrix $A=\\left[\\begin{array}{cc}2 & 3\\\\4 & 6\\\\\\end{array}\\right]$.\n", "\n", "* Find eigen values and eigen vector of A using the linalg.eig function.\n", "* Store the eigen values in a variable called B and eigen vectors in a variable C.\n", "* Print B and C." ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": true, "tags": [ "l2", "ce", "s2" ] }, "outputs": [], "source": [ "from scipy import linalg as LA\n", "import numpy as np\n", "\n", "A = np.array([2,3,4,6]).reshape(2,2)" ] }, { "cell_type": "markdown", "metadata": { "tags": [ "l2", "s2", "hint" ] }, "source": [ "### Hint" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "tags": [ "l2", "s2", "ans" ] }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Eigen Values: [ 0.+0.j 8.+0.j] \n", "Eigen Vectors: [[-0.83205029 -0.4472136 ]\n", " [ 0.5547002 -0.89442719]]\n" ] } ], "source": [ "B, C= LA.eig(A)\n", "\n", "print(\"Eigen Values: \",B,\"\\nEigen Vectors: \",C)" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "tags": [ "l2", "hid", "s2" ] }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "continue\n" ] } ], "source": [ "ref_tmp_var = False\n", "\n", "try:\n", " import numpy as np\n", "\n", " if np.all(B == [ 0.+0.j , 8.+0.j]) :\n", " ref_assert_var = True\n", " ref_tmp_var = True\n", " else:\n", " ref_assert_var = False\n", " print('Please follow the instructions given and use the same variables provided in the instructions. ')\n", "except Exception:\n", " print('Please follow the instructions given and use the same variables provided in the instructions. ')\n", "\n", "assert ref_tmp_var" ] } ], "metadata": { "executed_sections": [], "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.1" } }, "nbformat": 4, "nbformat_minor": 2 }