{
"cells": [
{
"cell_type": "markdown",
"id": "856eb195",
"metadata": {},
"source": [
"# Linear Equations and Matrix Algebra\n",
"\n",
"\n",
""
]
},
{
"cell_type": "markdown",
"id": "783b811b",
"metadata": {},
"source": [
"## Overview\n",
"\n",
"Many problems in economics and finance require solving linear equations.\n",
"\n",
"In this lecture we discuss linear equations and their applications.\n",
"\n",
"To illustrate the importance of linear equations, we begin with a two good\n",
"model of supply and demand.\n",
"\n",
"The two good case is so simple that solutions can be calculated by hand.\n",
"\n",
"But often we need to consider markets containing many goods.\n",
"\n",
"In the multiple goods case we face large systems of linear equations, with many equations\n",
"and unknowns.\n",
"\n",
"To handle such systems we need two things:\n",
"\n",
"- matrix algebra (and the knowledge of how to use it) plus \n",
"- computer code to apply matrix algebra to the problems of interest. \n",
"\n",
"\n",
"This lecture covers these steps.\n",
"\n",
"We will use the following packages:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "b64780e1",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"import numpy as np\n",
"import matplotlib.pyplot as plt"
]
},
{
"cell_type": "markdown",
"id": "05134b2e",
"metadata": {},
"source": [
"## A two good example\n",
"\n",
"In this section we discuss a simple two good example and solve it by\n",
"\n",
"1. pencil and paper \n",
"1. matrix algebra \n",
"\n",
"\n",
"The second method is more general, as we will see."
]
},
{
"cell_type": "markdown",
"id": "5be9c363",
"metadata": {},
"source": [
"### Pencil and paper methods\n",
"\n",
"Suppose that we have two related goods, such as\n",
"\n",
"- propane and ethanol, and \n",
"- rice and wheat, etc. \n",
"\n",
"\n",
"To keep things simple, we label them as good 0 and good 1.\n",
"\n",
"The demand for each good depends on the price of both goods:\n",
"\n",
"\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
" q_0^d = 100 - 10 p_0 - 5 p_1 \\\\\n",
" q_1^d = 50 - p_0 - 10 p_1\n",
"\\end{aligned} \\tag{8.1}\n",
"$$\n",
"\n",
"(We are assuming demand decreases when the price of either good goes up, but\n",
"other cases are also possible.)\n",
"\n",
"Let’s suppose that supply is given by\n",
"\n",
"\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
" q_0^s = 10 p_0 + 5 p_1 \\\\\n",
" q_1^s = 5 p_0 + 10 p_1\n",
"\\end{aligned} \\tag{8.2}\n",
"$$\n",
"\n",
"Equilibrium holds when supply equals demand ($ q_0^s = q_0^d $ and $ q_1^s = q_1^d $).\n",
"\n",
"This yields the linear system\n",
"\n",
"\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
" 100 - 10 p_0 - 5 p_1 = 10 p_0 + 5 p_1 \\\\\n",
" 50 - p_0 - 10 p_1 = 5 p_0 + 10 p_1\n",
"\\end{aligned} \\tag{8.3}\n",
"$$\n",
"\n",
"We can solve this with pencil and paper to get\n",
"\n",
"$$\n",
"p_0 = 4.41 \\quad \\text{and} \\quad p_1 = 1.18.\n",
"$$\n",
"\n",
"Inserting these results into either [(8.1)](#equation-two-eq-demand) or [(8.2)](#equation-two-eq-supply) yields the\n",
"equilibrium quantities\n",
"\n",
"$$\n",
"q_0 = 50 \\quad \\text{and} \\quad q_1 = 33.82.\n",
"$$"
]
},
{
"cell_type": "markdown",
"id": "671485df",
"metadata": {},
"source": [
"### Looking forward\n",
"\n",
"Pencil and paper methods are easy in the two good case.\n",
"\n",
"But what if there are many goods?\n",
"\n",
"For such problems we need matrix algebra.\n",
"\n",
"Before solving problems with matrix algebra, let’s first recall the\n",
"basics of vectors and matrices, in both theory and computation."
]
},
{
"cell_type": "markdown",
"id": "7f6ffbf2",
"metadata": {},
"source": [
"## Vectors\n",
"\n",
"\n",
"\n",
"A **vector** of length $ n $ is just a sequence (or array, or tuple) of $ n $ numbers, which we write as $ x = (x_1, \\ldots, x_n) $ or $ x = \\begin{bmatrix}x_1, \\ldots, x_n\\end{bmatrix} $.\n",
"\n",
"We can write these sequences either horizontally or vertically.\n",
"\n",
"But when we use matrix operations, our default assumption is that vectors are\n",
"column vectors.\n",
"\n",
"The set of all $ n $-vectors is denoted by $ \\mathbb R^n $."
]
},
{
"cell_type": "markdown",
"id": "a6103bec",
"metadata": {},
"source": [
"## \n",
"\n",
"- $ \\mathbb R^2 $ is the plane — the set of pairs $ (x_1, x_2) $. \n",
"- $ \\mathbb R^3 $ is 3 dimensional space — the set of vectors $ (x_1, x_2, x_3) $. \n",
"\n",
"\n",
"Often vectors are represented visually as arrows from the origin to the point.\n",
"\n",
"Here’s a visualization."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c1b2c15a",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"fig, ax = plt.subplots()\n",
"# Set the axes through the origin\n",
"for spine in ['left', 'bottom']:\n",
" ax.spines[spine].set_position('zero')\n",
"for spine in ['right', 'top']:\n",
" ax.spines[spine].set_color('none')\n",
"\n",
"ax.set(xlim=(-5, 5), ylim=(-5, 5))\n",
"\n",
"vecs = ((2, 4), (-3, 3), (-4, -3.5))\n",
"for v in vecs:\n",
" ax.annotate('', xy=v, xytext=(0, 0),\n",
" arrowprops=dict(facecolor='blue',\n",
" shrink=0,\n",
" alpha=0.7,\n",
" width=0.5))\n",
" ax.text(1.1 * v[0], 1.1 * v[1], str(v))\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"id": "18f25b80",
"metadata": {},
"source": [
"### Vector operations\n",
"\n",
"\n",
"\n",
"Sometimes we want to modify vectors.\n",
"\n",
"The two most common operators on vectors are addition and scalar\n",
"multiplication, which we now describe.\n",
"\n",
"When we add two vectors, we add them element-by-element."
]
},
{
"cell_type": "markdown",
"id": "a34e5785",
"metadata": {},
"source": [
"### \n",
"\n",
"$$\n",
"\\begin{bmatrix}\n",
" 4 \\\\\n",
" -2 \n",
"\\end{bmatrix}\n",
"+\n",
"\\begin{bmatrix}\n",
" 3 \\\\\n",
" 3 \n",
"\\end{bmatrix}\n",
"=\n",
"\\begin{bmatrix}\n",
" 4 & + & 3 \\\\\n",
" -2 & + & 3 \n",
"\\end{bmatrix}\n",
"=\n",
"\\begin{bmatrix}\n",
" 7 \\\\\n",
" 1\n",
"\\end{bmatrix}.\n",
"$$\n",
"\n",
"In general,\n",
"\n",
"$$\n",
"x + y =\n",
"\\begin{bmatrix}\n",
" x_1 \\\\\n",
" x_2 \\\\\n",
" \\vdots \\\\\n",
" x_n\n",
"\\end{bmatrix} +\n",
"\\begin{bmatrix}\n",
" y_1 \\\\\n",
" y_2 \\\\\n",
" \\vdots \\\\\n",
" y_n\n",
"\\end{bmatrix} :=\n",
"\\begin{bmatrix}\n",
" x_1 + y_1 \\\\\n",
" x_2 + y_2 \\\\\n",
" \\vdots \\\\\n",
" x_n + y_n\n",
"\\end{bmatrix}.\n",
"$$\n",
"\n",
"We can visualise vector addition in $ \\mathbb{R}^2 $ as follows."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "1188bfa6",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"fig, ax = plt.subplots()\n",
"# Set the axes through the origin\n",
"for spine in ['left', 'bottom']:\n",
" ax.spines[spine].set_position('zero')\n",
"for spine in ['right', 'top']:\n",
" ax.spines[spine].set_color('none')\n",
"\n",
"ax.set(xlim=(-2, 10), ylim=(-4, 4))\n",
"# ax.grid()\n",
"vecs = ((4, -2), (3, 3), (7, 1))\n",
"tags = ('(x1, x2)', '(y1, y2)', '(x1+x2, y1+y2)')\n",
"colors = ('blue', 'green', 'red')\n",
"for i, v in enumerate(vecs):\n",
" ax.annotate('', xy=v, xytext=(0, 0),\n",
" arrowprops=dict(color=colors[i],\n",
" shrink=0,\n",
" alpha=0.7,\n",
" width=0.5,\n",
" headwidth=8,\n",
" headlength=15))\n",
" ax.text(v[0] + 0.2, v[1] + 0.1, tags[i])\n",
"\n",
"for i, v in enumerate(vecs):\n",
" ax.annotate('', xy=(7, 1), xytext=v,\n",
" arrowprops=dict(color='gray',\n",
" shrink=0,\n",
" alpha=0.3,\n",
" width=0.5,\n",
" headwidth=5,\n",
" headlength=20))\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"id": "e6e86843",
"metadata": {},
"source": [
"Scalar multiplication is an operation that multiplies a vector $ x $ with a scalar elementwise."
]
},
{
"cell_type": "markdown",
"id": "40a653cf",
"metadata": {},
"source": [
"### \n",
"\n",
"$$\n",
"-2\n",
"\\begin{bmatrix}\n",
" 3 \\\\\n",
" -7 \n",
"\\end{bmatrix}\n",
"=\n",
"\\begin{bmatrix}\n",
" -2 & \\times & 3 \\\\\n",
" -2 & \\times & -7\n",
"\\end{bmatrix}\n",
"=\n",
"\\begin{bmatrix}\n",
" -6 \\\\\n",
" 14\n",
"\\end{bmatrix}.\n",
"$$\n",
"\n",
"More generally, it takes a number $ \\gamma $ and a vector $ x $ and produces\n",
"\n",
"$$\n",
"\\gamma x :=\n",
"\\begin{bmatrix}\n",
" \\gamma x_1 \\\\\n",
" \\gamma x_2 \\\\\n",
" \\vdots \\\\\n",
" \\gamma x_n\n",
"\\end{bmatrix}.\n",
"$$\n",
"\n",
"Scalar multiplication is illustrated in the next figure."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "1d864612",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"fig, ax = plt.subplots()\n",
"# Set the axes through the origin\n",
"for spine in ['left', 'bottom']:\n",
" ax.spines[spine].set_position('zero')\n",
"for spine in ['right', 'top']:\n",
" ax.spines[spine].set_color('none')\n",
"\n",
"ax.set(xlim=(-5, 5), ylim=(-5, 5))\n",
"x = (2, 2)\n",
"ax.annotate('', xy=x, xytext=(0, 0),\n",
" arrowprops=dict(facecolor='blue',\n",
" shrink=0,\n",
" alpha=1,\n",
" width=0.5))\n",
"ax.text(x[0] + 0.4, x[1] - 0.2, '$x$', fontsize='16')\n",
"\n",
"scalars = (-2, 2)\n",
"x = np.array(x)\n",
"\n",
"for s in scalars:\n",
" v = s * x\n",
" ax.annotate('', xy=v, xytext=(0, 0),\n",
" arrowprops=dict(facecolor='red',\n",
" shrink=0,\n",
" alpha=0.5,\n",
" width=0.5))\n",
" ax.text(v[0] + 0.4, v[1] - 0.2, f'${s} x$', fontsize='16')\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"id": "48f08506",
"metadata": {},
"source": [
"In Python, a vector can be represented as a list or tuple,\n",
"such as `x = [2, 4, 6]` or `x = (2, 4, 6)`.\n",
"\n",
"However, it is more common to represent vectors with\n",
"[NumPy arrays](https://python-programming.quantecon.org/numpy.html#numpy-arrays).\n",
"\n",
"One advantage of NumPy arrays is that scalar multiplication and addition have\n",
"very natural syntax."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "78092e23",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"x = np.ones(3) # Vector of three ones\n",
"y = np.array((2, 4, 6)) # Converts tuple (2, 4, 6) into a NumPy array\n",
"x + y # Add (element-by-element)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e885a052",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"4 * x # Scalar multiply"
]
},
{
"cell_type": "markdown",
"id": "44059302",
"metadata": {},
"source": [
"### Inner product and norm\n",
"\n",
"\n",
"\n",
"The **inner product** of vectors $ x,y \\in \\mathbb R^n $ is defined as\n",
"\n",
"$$\n",
"x^\\top y = \n",
"\\begin{bmatrix}\n",
" \\color{red}{x_1} & \\color{blue}{x_2} & \\cdots & x_n\n",
"\\end{bmatrix}\n",
"\\begin{bmatrix}\n",
" \\color{red}{y_1} \\\\\n",
" \\color{blue}{y_2} \\\\\n",
" \\vdots \\\\\n",
" y_n\n",
"\\end{bmatrix}\n",
"= {\\color{red}{x_1 y_1}} + {\\color{blue}{x_2 y_2}} + \\cdots + x_n y_n\n",
":= \\sum_{i=1}^n x_i y_i.\n",
"$$\n",
"\n",
"The **norm** of a vector $ x $ represents its “length” (i.e., its distance from\n",
"the zero vector) and is defined as\n",
"\n",
"$$\n",
"\\| x \\| := \\sqrt{x^\\top x} := \\left( \\sum_{i=1}^n x_i^2 \\right)^{1/2}.\n",
"$$\n",
"\n",
"The expression $ \\| x - y\\| $ can be thought of as the “distance” between $ x $ and $ y $.\n",
"\n",
"The inner product and norm can be computed as follows"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "4c814535",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"np.sum(x*y) # Inner product of x and y"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6ec72e23",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"x @ y # Another way to compute the inner product "
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "24cbcdc1",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"np.sqrt(np.sum(x**2)) # Norm of x, method one"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e2cbc2b0",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"np.linalg.norm(x) # Norm of x, method two"
]
},
{
"cell_type": "markdown",
"id": "6d2882b0",
"metadata": {},
"source": [
"## Matrix operations\n",
"\n",
"\n",
"\n",
"When we discussed linear price systems, we mentioned using matrix algebra.\n",
"\n",
"Matrix algebra is similar to algebra for numbers.\n",
"\n",
"Let’s review some details."
]
},
{
"cell_type": "markdown",
"id": "d34cd35f",
"metadata": {},
"source": [
"### Addition and scalar multiplication\n",
"\n",
"Just as was the case for vectors, we can add, subtract and scalar multiply\n",
"matrices.\n",
"\n",
"Scalar multiplication and addition are generalizations of the vector case:"
]
},
{
"cell_type": "markdown",
"id": "ff2bde35",
"metadata": {},
"source": [
"### \n",
"\n",
"$$\n",
"3\n",
"\\begin{bmatrix}\n",
" 2 & -13 \\\\\n",
" 0 & 5\n",
"\\end{bmatrix}\n",
"=\n",
"\\begin{bmatrix}\n",
" 6 & -39 \\\\\n",
" 0 & 15\n",
"\\end{bmatrix}.\n",
"$$\n",
"\n",
"In general for a number $ \\gamma $ and any matrix $ A $,\n",
"\n",
"$$\n",
"\\gamma A =\n",
"\\gamma\n",
"\\begin{bmatrix}\n",
" a_{11} & \\cdots & a_{1k} \\\\\n",
" \\vdots & \\vdots & \\vdots \\\\\n",
" a_{n1} & \\cdots & a_{nk}\n",
"\\end{bmatrix} :=\n",
"\\begin{bmatrix}\n",
" \\gamma a_{11} & \\cdots & \\gamma a_{1k} \\\\\n",
" \\vdots & \\vdots & \\vdots \\\\\n",
" \\gamma a_{n1} & \\cdots & \\gamma a_{nk}\n",
"\\end{bmatrix}.\n",
"$$"
]
},
{
"cell_type": "markdown",
"id": "4d3e848f",
"metadata": {},
"source": [
"### \n",
"\n",
"Consider this example of matrix addition,\n",
"\n",
"$$\n",
"\\begin{bmatrix}\n",
" 1 & 5 \\\\\n",
" 7 & 3 \\\\\n",
"\\end{bmatrix}\n",
"+\n",
"\\begin{bmatrix}\n",
" 12 & -1 \\\\\n",
" 0 & 9\n",
"\\end{bmatrix}\n",
"=\n",
"\\begin{bmatrix}\n",
" 13 & 4 \\\\\n",
" 7 & 12\n",
"\\end{bmatrix}.\n",
"$$\n",
"\n",
"In general,\n",
"\n",
"$$\n",
"A + B =\n",
"\\begin{bmatrix}\n",
" a_{11} & \\cdots & a_{1k} \\\\\n",
" \\vdots & \\vdots & \\vdots \\\\\n",
" a_{n1} & \\cdots & a_{nk}\n",
"\\end{bmatrix} +\n",
"\\begin{bmatrix}\n",
" b_{11} & \\cdots & b_{1k} \\\\\n",
" \\vdots & \\vdots & \\vdots \\\\\n",
" b_{n1} & \\cdots & b_{nk}\n",
"\\end{bmatrix} :=\n",
"\\begin{bmatrix}\n",
" a_{11} + b_{11} & \\cdots & a_{1k} + b_{1k} \\\\\n",
" \\vdots & \\vdots & \\vdots \\\\\n",
" a_{n1} + b_{n1} & \\cdots & a_{nk} + b_{nk}\n",
"\\end{bmatrix}.\n",
"$$\n",
"\n",
"In the latter case, the matrices must have the same shape in order for the\n",
"definition to make sense."
]
},
{
"cell_type": "markdown",
"id": "fa86d64f",
"metadata": {},
"source": [
"### Matrix multiplication\n",
"\n",
"We also have a convention for *multiplying* two matrices.\n",
"\n",
"The rule for matrix multiplication generalizes the idea of inner products\n",
"discussed above.\n",
"\n",
"If $ A $ and $ B $ are two matrices, then their product $ A B $ is formed by taking\n",
"as its $ i,j $-th element the inner product of the $ i $-th row of $ A $ and the\n",
"$ j $-th column of $ B $.\n",
"\n",
"If $ A $ is $ n \\times k $ and $ B $ is $ j \\times m $, then to multiply $ A $ and $ B $\n",
"we require $ k = j $, and the resulting matrix $ A B $ is $ n \\times m $."
]
},
{
"cell_type": "markdown",
"id": "fb912758",
"metadata": {},
"source": [
"### \n",
"\n",
"Here’s an example of a $ 2 \\times 2 $ matrix multiplied by a $ 2 \\times 1 $ vector.\n",
"\n",
"$$\n",
"Ax =\n",
"\\begin{bmatrix}\n",
" \\color{red}{a_{11}} & \\color{red}{a_{12}} \\\\\n",
" a_{21} & a_{22}\n",
"\\end{bmatrix}\n",
"\\begin{bmatrix}\n",
" \\color{red}{x_1} \\\\\n",
" \\color{red}{x_2}\n",
"\\end{bmatrix}\n",
"=\n",
"\\begin{bmatrix}\n",
" \\color{red}{a_{11}x_1 + a_{12}x_2} \\\\\n",
" a_{21}x_1 + a_{22}x_2\n",
"\\end{bmatrix}\n",
"$$\n",
"\n",
"As an important special case, consider multiplying $ n \\times k $\n",
"matrix $ A $ and $ k \\times 1 $ column vector $ x $.\n",
"\n",
"According to the preceding rule, this gives us an $ n \\times 1 $ column vector.\n",
"\n",
"\n",
"\n",
"$$\n",
"A x =\n",
"{\\begin{bmatrix}\n",
" a_{11} & a_{12} & \\cdots & a_{1k} \\\\\n",
" \\vdots & \\vdots & & \\vdots \\\\\n",
" \\color{red}{a_{i1}} & \\color{red}{a_{i2}} & \\color{red}{\\cdots} & \\color{red}{a_{i}k} \\\\\n",
" \\vdots & \\vdots & & \\vdots \\\\\n",
" a_{n1} & a_{n2} & \\cdots & a_{nk}\n",
"\\end{bmatrix}}_{n \\times k}\n",
"{\\begin{bmatrix}\n",
" \\color{red}{x_{1}} \\\\\n",
" \\color{red}{x_{2}} \\\\\n",
" \\color{red}{\\vdots} \\\\\n",
" \\color{red}{\\vdots} \\\\\n",
" \\color{red}{x_{k}}\n",
"\\end{bmatrix}}_{k \\times 1} :=\n",
"{\\begin{bmatrix}\n",
" a_{11} x_1 + a_{22} x_2 + \\cdots + a_{1k} x_k \\\\\n",
" \\vdots \\\\\n",
" \\color{red}{a_{i1} x_1 + a_{i2} x_2 + \\cdots + a_{ik} x_k} \\\\\n",
" \\vdots \\\\\n",
" a_{n1} x_1 + a_{n2} x_2 + \\cdots + a_{nk} x_k\n",
"\\end{bmatrix}}_{n \\times 1} \\tag{8.4}\n",
"$$\n",
"\n",
"Here is a simple illustration of multiplication of two matrices.\n",
"\n",
"$$\n",
"AB =\n",
"\\begin{bmatrix}\n",
" a_{11} & a_{12} \\\\\n",
" \\color{red}{a_{21}} & \\color{red}{a_{22}} \\\\\n",
"\\end{bmatrix}\n",
"\\begin{bmatrix}\n",
" b_{11} & \\color{red}{b_{12}} \\\\\n",
" b_{21} & \\color{red}{b_{22}} \\\\\n",
"\\end{bmatrix} :=\n",
"\\begin{bmatrix}\n",
" a_{11}b_{11} + a_{12}b_{21} & a_{11}b_{12} + a_{12}b_{22} \\\\\n",
" a_{21}b_{11} + a_{22}b_{21} & \\color{red}{a_{21}b_{12} + a_{22}b_{22}}\n",
"\\end{bmatrix}\n",
"$$\n",
"\n",
"There are many tutorials to help you further visualize this operation, such as\n",
"\n",
"- [this one](http://www.mathsisfun.com/algebra/matrix-multiplying.html), or \n",
"- the discussion on the [Wikipedia page](https://en.wikipedia.org/wiki/Matrix_multiplication). \n",
"\n",
"\n",
">**Note**\n",
">\n",
">Unlike number products, $ A B $ and $ B A $ are not generally the same thing.\n",
"\n",
"One important special case is the [identity matrix](https://en.wikipedia.org/wiki/Identity_matrix), which has ones on the principal diagonal and zero elsewhere:\n",
"\n",
"$$\n",
"I = \n",
" \\begin{bmatrix}\n",
" 1 & \\cdots & 0 \\\\\n",
" \\vdots & \\ddots & \\vdots \\\\\n",
" 0 & \\cdots & 1\n",
" \\end{bmatrix}\n",
"$$\n",
"\n",
"It is a useful exercise to check the following:\n",
"\n",
"- if $ A $ is $ n \\times k $ and $ I $ is the $ k \\times k $ identity matrix, then $ AI = A $, and \n",
"- if $ I $ is the $ n \\times n $ identity matrix, then $ IA = A $. "
]
},
{
"cell_type": "markdown",
"id": "2ef4aca3",
"metadata": {},
"source": [
"### Matrices in NumPy\n",
"\n",
"\n",
"\n",
"NumPy arrays are also used as matrices, and have fast, efficient functions and methods for all the standard matrix operations.\n",
"\n",
"You can create them manually from tuples of tuples (or lists of lists) as follows"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "87fb7076",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"A = ((1, 2),\n",
" (3, 4))\n",
"\n",
"type(A)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "3cece233",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"A = np.array(A)\n",
"\n",
"type(A)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "0109b180",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"A.shape"
]
},
{
"cell_type": "markdown",
"id": "5b7c9f93",
"metadata": {},
"source": [
"The `shape` attribute is a tuple giving the number of rows and columns —\n",
"see [here](https://python-programming.quantecon.org/numpy.html#shape-and-dimension)\n",
"for more discussion.\n",
"\n",
"To get the transpose of `A`, use `A.transpose()` or, more simply, `A.T`.\n",
"\n",
"There are many convenient functions for creating common matrices (matrices of zeros,\n",
"ones, etc.) — see [here](https://python-programming.quantecon.org/numpy.html#creating-arrays).\n",
"\n",
"Since operations are performed elementwise by default, scalar multiplication and addition have very natural syntax."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "f54eedba",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"A = np.identity(3) # 3 x 3 identity matrix\n",
"B = np.ones((3, 3)) # 3 x 3 matrix of ones\n",
"2 * A"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c6bde72a",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"A + B"
]
},
{
"cell_type": "markdown",
"id": "73cbcc37",
"metadata": {},
"source": [
"To multiply matrices we use the `@` symbol.\n",
"\n",
">**Note**\n",
">\n",
">In particular, `A @ B` is matrix multiplication, whereas `A * B` is element-by-element multiplication."
]
},
{
"cell_type": "markdown",
"id": "b52615b9",
"metadata": {},
"source": [
"### Two good model in matrix form\n",
"\n",
"We can now revisit the two good model and solve [(8.3)](#equation-two-equilibrium)\n",
"numerically via matrix algebra.\n",
"\n",
"This involves some extra steps but the method is widely applicable — as we\n",
"will see when we include more goods.\n",
"\n",
"First we rewrite [(8.1)](#equation-two-eq-demand) as\n",
"\n",
"\n",
"\n",
"$$\n",
"q^d = D p + h\n",
" \\quad \\text{where} \\quad\n",
" q^d = \n",
" \\begin{bmatrix}\n",
" q_0^d \\\\\n",
" q_1^d\n",
" \\end{bmatrix}\n",
" \\quad\n",
" D = \n",
" \\begin{bmatrix}\n",
" -10 & - 5 \\\\\n",
" - 1 & - 10 \n",
" \\end{bmatrix}\n",
" \\quad \\text{and} \\quad\n",
" h =\n",
" \\begin{bmatrix}\n",
" 100 \\\\\n",
" 50\n",
" \\end{bmatrix}. \\tag{8.5}\n",
"$$\n",
"\n",
"Recall that $ p \\in \\mathbb{R}^{2} $ is the price of two goods.\n",
"\n",
"(Please check that $ q^d = D p + h $ represents the same equations as [(8.1)](#equation-two-eq-demand).)\n",
"\n",
"We rewrite [(8.2)](#equation-two-eq-supply) as\n",
"\n",
"\n",
"\n",
"$$\n",
"q^s = C p \n",
" \\quad \\text{where} \\quad\n",
" q^s = \n",
" \\begin{bmatrix}\n",
" q_0^s \\\\\n",
" q_1^s\n",
" \\end{bmatrix}\n",
" \\quad \\text{and} \\quad\n",
" C = \n",
" \\begin{bmatrix}\n",
" 10 & 5 \\\\\n",
" 5 & 10 \n",
" \\end{bmatrix}. \\tag{8.6}\n",
"$$\n",
"\n",
"Now equality of supply and demand can be expressed as $ q^s = q^d $, or\n",
"\n",
"$$\n",
"C p = D p + h.\n",
"$$\n",
"\n",
"We can rearrange the terms to get\n",
"\n",
"$$\n",
"(C - D) p = h.\n",
"$$\n",
"\n",
"If all of the terms were numbers, we could solve for prices as $ p = h /\n",
"(C-D) $.\n",
"\n",
"Matrix algebra allows us to do something similar: we can solve for equilibrium\n",
"prices using the inverse of $ C - D $:\n",
"\n",
"\n",
"\n",
"$$\n",
"p = (C - D)^{-1} h. \\tag{8.7}\n",
"$$\n",
"\n",
"Before we implement the solution let us consider a more general setting."
]
},
{
"cell_type": "markdown",
"id": "b3149a59",
"metadata": {},
"source": [
"### More goods\n",
"\n",
"It is natural to think about demand systems with more goods.\n",
"\n",
"For example, even within energy commodities there are many different goods,\n",
"including crude oil, gasoline, coal, natural gas, ethanol, and uranium.\n",
"\n",
"The prices of these goods are related, so it makes sense to study them\n",
"together.\n",
"\n",
"Pencil and paper methods become very time consuming with large systems.\n",
"\n",
"But fortunately the matrix methods described above are essentially unchanged.\n",
"\n",
"In general, we can write the demand equation as $ q^d = Dp + h $, where\n",
"\n",
"- $ q^d $ is an $ n \\times 1 $ vector of demand quantities for $ n $ different goods. \n",
"- $ D $ is an $ n \\times n $ “coefficient” matrix. \n",
"- $ h $ is an $ n \\times 1 $ vector of constant values. \n",
"\n",
"\n",
"Similarly, we can write the supply equation as $ q^s = Cp + e $, where\n",
"\n",
"- $ q^s $ is an $ n \\times 1 $ vector of supply quantities for the same goods. \n",
"- $ C $ is an $ n \\times n $ “coefficient” matrix. \n",
"- $ e $ is an $ n \\times 1 $ vector of constant values. \n",
"\n",
"\n",
"To find an equilibrium, we solve $ Dp + h = Cp + e $, or\n",
"\n",
"\n",
"\n",
"$$\n",
"(D- C)p = e - h. \\tag{8.8}\n",
"$$\n",
"\n",
"Then the price vector of the n different goods is\n",
"\n",
"$$\n",
"p = (D- C)^{-1}(e - h).\n",
"$$"
]
},
{
"cell_type": "markdown",
"id": "91094359",
"metadata": {},
"source": [
"### General linear systems\n",
"\n",
"A more general version of the problem described above looks as follows.\n",
"\n",
"\n",
"\n",
"$$\n",
"\\begin{matrix}\n",
" a_{11} x_1 & + & a_{12} x_2 & + & \\cdots & + & a_{1n} x_n & = & b_1 \\\\\n",
" \\vdots & & \\vdots & & & & \\vdots & & \\vdots \\\\\n",
" a_{n1} x_1 & + & a_{n2} x_2 & + & \\cdots & + & a_{nn} x_n & = & b_n\n",
"\\end{matrix} \\tag{8.9}\n",
"$$\n",
"\n",
"The objective here is to solve for the “unknowns” $ x_1, \\ldots, x_n $.\n",
"\n",
"We take as given the coefficients $ a_{11}, \\ldots, a_{nn} $ and constants $ b_1, \\ldots, b_n $.\n",
"\n",
"Notice that we are treating a setting where the number of unknowns equals the\n",
"number of equations.\n",
"\n",
"This is the case where we are most likely to find a well-defined solution.\n",
"\n",
"(The other cases are referred to as [overdetermined](https://en.wikipedia.org/wiki/Overdetermined_system) and [underdetermined](https://en.wikipedia.org/wiki/Underdetermined_system) systems\n",
"of equations — we defer discussion of these cases until later lectures.)\n",
"\n",
"In matrix form, the system [(8.9)](#equation-la-se) becomes\n",
"\n",
"\n",
"\n",
"$$\n",
"A x = b\n",
" \\quad \\text{where} \\quad\n",
" A = \n",
" \\begin{bmatrix}\n",
" a_{11} & \\cdots & a_{1n} \\\\\n",
" \\vdots & \\vdots & \\vdots \\\\\n",
" a_{n1} & \\cdots & a_{nn}\n",
" \\end{bmatrix}\n",
" \\quad \\text{and} \\quad\n",
" b =\n",
" \\begin{bmatrix}\n",
" b_1 \\\\\n",
" \\vdots \\\\\n",
" b_n\n",
" \\end{bmatrix}. \\tag{8.10}\n",
"$$"
]
},
{
"cell_type": "markdown",
"id": "993d6ee1",
"metadata": {},
"source": [
"### \n",
"\n",
"For example, [(8.8)](#equation-n-eq-sys-la) has this form with\n",
"\n",
"$$\n",
"A = D - C, \n",
" \\quad\n",
" b = e - h\n",
" \\quad \\text{and} \\quad\n",
" x = p.\n",
"$$\n",
"\n",
"When considering problems such as [(8.10)](#equation-la-gf), we need to ask at least some of\n",
"the following questions\n",
"\n",
"- Does a solution actually exist? \n",
"- If a solution exists, how should we compute it? "
]
},
{
"cell_type": "markdown",
"id": "9fdb9b02",
"metadata": {},
"source": [
"## Solving systems of equations\n",
"\n",
"\n",
"\n",
"Recall again the system of equations [(8.9)](#equation-la-se), which we write here again as\n",
"\n",
"\n",
"\n",
"$$\n",
"A x = b. \\tag{8.11}\n",
"$$\n",
"\n",
"The problem we face is to find a vector $ x \\in \\mathbb R^n $ that solves\n",
"[(8.11)](#equation-la-se2), taking $ b $ and $ A $ as given.\n",
"\n",
"We may not always find a unique vector $ x $ that solves [(8.11)](#equation-la-se2).\n",
"\n",
"We illustrate two such cases below."
]
},
{
"cell_type": "markdown",
"id": "589a85a9",
"metadata": {},
"source": [
"### No solution\n",
"\n",
"Consider the system of equations given by,\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
" x + 3y &= 3 \\\\\n",
" 2x + 6y &= -8.\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"It can be verified manually that this system has no possible solution.\n",
"\n",
"To illustrate why this situation arises let’s plot the two lines."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6d88c0c9",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"fig, ax = plt.subplots()\n",
"x = np.linspace(-10, 10)\n",
"plt.plot(x, (3-x)/3, label=f'$x + 3y = 3$')\n",
"plt.plot(x, (-8-2*x)/6, label=f'$2x + 6y = -8$')\n",
"plt.legend()\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"id": "f788c503",
"metadata": {},
"source": [
"Clearly, these are parallel lines and hence we will never find a point $ x \\in \\mathbb{R}^2 $\n",
"such that these lines intersect.\n",
"\n",
"Thus, this system has no possible solution.\n",
"\n",
"We can rewrite this system in matrix form as\n",
"\n",
"\n",
"\n",
"$$\n",
"A x = b\n",
" \\quad \\text{where} \\quad\n",
" A =\n",
" \\begin{bmatrix}\n",
" 1 & 3 \\\\\n",
" 2 & 6 \n",
" \\end{bmatrix}\n",
" \\quad \\text{and} \\quad\n",
" b =\n",
" \\begin{bmatrix}\n",
" 3 \\\\\n",
" -8\n",
" \\end{bmatrix}. \\tag{8.12}\n",
"$$\n",
"\n",
"It can be noted that the $ 2^{nd} $ row of matrix $ A = (2, 6) $ is just a scalar multiple of the $ 1^{st} $ row of matrix $ A = (1, 3) $.\n",
"\n",
"The rows of matrix $ A $ in this case are called **linearly dependent.**\n",
"\n",
">**Note**\n",
">\n",
">Advanced readers can find a detailed explanation of linear dependence and\n",
"independence [here](https://python.quantecon.org/linear_algebra.html#linear-independence).\n",
"\n",
"But these details are not needed in what follows."
]
},
{
"cell_type": "markdown",
"id": "0e3c1e5c",
"metadata": {},
"source": [
"### Many solutions\n",
"\n",
"Now consider,\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
" x - 2y &= -4 \\\\\n",
" -2x + 4y &= 8.\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"Any vector $ v = (x,y) $ such that $ x = 2y - 4 $ will solve the above system.\n",
"\n",
"Since we can find infinite such vectors this system has infinitely many solutions.\n",
"\n",
"This is because the rows of the corresponding matrix\n",
"\n",
"\n",
"\n",
"$$\n",
"A =\n",
" \\begin{bmatrix}\n",
" 1 & -2 \\\\\n",
" -2 & 4\n",
" \\end{bmatrix}. \\tag{8.13}\n",
"$$\n",
"\n",
"are linearly dependent — can you see why?\n",
"\n",
"We now impose conditions on $ A $ in [(8.11)](#equation-la-se2) that rule out these problems."
]
},
{
"cell_type": "markdown",
"id": "b3f84062",
"metadata": {},
"source": [
"### Nonsingular matrices\n",
"\n",
"To every square matrix we can assign a unique number called the\n",
"[determinant](https://en.wikipedia.org/wiki/Determinant).\n",
"\n",
"For $ 2 \\times 2 $ matrices, the determinant is given by,\n",
"\n",
"$$\n",
"\\begin{bmatrix}\n",
" \\color{red}{a} & \\color{blue}{b} \\\\\n",
" \\color{blue}{c} & \\color{red}{d}\n",
"\\end{bmatrix}\n",
"=\n",
"{\\color{red}{ad}} - {\\color{blue}{bc}}.\n",
"$$\n",
"\n",
"If the determinant of $ A $ is not zero, then we say that $ A $ is *nonsingular*.\n",
"\n",
"A square matrix $ A $ is nonsingular if and only if the rows and columns of $ A $\n",
"are linearly independent.\n",
"\n",
"A more detailed explanation of matrix inverse can be found [here](https://www.mathsisfun.com/algebra/matrix-inverse.html).\n",
"\n",
"You can check yourself that the in [(8.12)](#equation-no-soln) and [(8.13)](#equation-many-solns) with\n",
"linearly dependent rows are singular matrices.\n",
"\n",
"This gives us a useful one-number summary of whether or not a square matrix\n",
"can be inverted.\n",
"\n",
"In particular, a square matrix $ A $ has a nonzero determinant, if and only if\n",
"it possesses an *inverse matrix* $ A^{-1} $, with the property that $ A A^{-1} =\n",
"A^{-1} A = I $.\n",
"\n",
"As a consequence, if we pre-multiply both sides of $ Ax = b $ by $ A^{-1} $, we\n",
"get\n",
"\n",
"\n",
"\n",
"$$\n",
"x = A^{-1} b. \\tag{8.14}\n",
"$$\n",
"\n",
"This is the solution to $ Ax = b $ — the solution we are looking for."
]
},
{
"cell_type": "markdown",
"id": "10ebf8fc",
"metadata": {},
"source": [
"### Linear equations with NumPy\n",
"\n",
"\n",
"\n",
"In the two good example we obtained the matrix equation,\n",
"\n",
"$$\n",
"p = (C-D)^{-1} h.\n",
"$$\n",
"\n",
"where $ C $, $ D $ and $ h $ are given by [(8.5)](#equation-two-eq-demand-mat) and [(8.6)](#equation-two-eq-supply-mat).\n",
"\n",
"This equation is analogous to [(8.14)](#equation-la-se-inv) with $ A = (C-D)^{-1} $, $ b = h $, and $ x = p $.\n",
"\n",
"We can now solve for equilibrium prices with NumPy’s `linalg` submodule.\n",
"\n",
"All of these routines are Python front ends to time-tested and highly optimized FORTRAN code."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "480b8a36",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"C = ((10, 5), # Matrix C\n",
" (5, 10))"
]
},
{
"cell_type": "markdown",
"id": "e1036e08",
"metadata": {},
"source": [
"Now we change this to a NumPy array."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "80a3ad3b",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"C = np.array(C)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "be21877e",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"D = ((-10, -5), # Matrix D\n",
" (-1, -10))\n",
"D = np.array(D)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c4ef6d11",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"h = np.array((100, 50)) # Vector h\n",
"h.shape = 2,1 # Transforming h to a column vector"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c7c0b90f",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"from numpy.linalg import det, inv\n",
"A = C - D\n",
"# Check that A is nonsingular (non-zero determinant), and hence invertible\n",
"det(A)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "63932e25",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"A_inv = inv(A) # compute the inverse\n",
"A_inv"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "3d147f8e",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"p = A_inv @ h # equilibrium prices\n",
"p"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "799a6f2d",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"q = C @ p # equilibrium quantities\n",
"q"
]
},
{
"cell_type": "markdown",
"id": "a4286faf",
"metadata": {},
"source": [
"Notice that we get the same solutions as the pencil and paper case.\n",
"\n",
"We can also solve for $ p $ using `solve(A, h)` as follows."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "f47a5944",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"from numpy.linalg import solve\n",
"p = solve(A, h) # equilibrium prices\n",
"p"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "31846918",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"q = C @ p # equilibrium quantities\n",
"q"
]
},
{
"cell_type": "markdown",
"id": "4721d0b4",
"metadata": {},
"source": [
"Observe how we can solve for $ x = A^{-1} y $ by either via `inv(A) @ y`, or using `solve(A, y)`.\n",
"\n",
"The latter method uses a different algorithm that is numerically more stable and hence should be the default option."
]
},
{
"cell_type": "markdown",
"id": "814e8a01",
"metadata": {},
"source": [
"## Exercises"
]
},
{
"cell_type": "markdown",
"id": "42445034",
"metadata": {},
"source": [
"## Exercise 8.1\n",
"\n",
"Let’s consider a market with 3 commodities - good 0, good 1 and good 2.\n",
"\n",
"The demand for each good depends on the price of the other two goods and is given by:\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
" q_0^d & = 90 - 15p_0 + 5p_1 + 5p_2 \\\\\n",
" q_1^d & = 60 + 5p_0 - 10p_1 + 10p_2 \\\\\n",
" q_2^d & = 50 + 5p_0 + 5p_1 - 5p_2\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"(Here demand decreases when own price increases but increases when prices of other goods increase.)\n",
"\n",
"The supply of each good is given by:\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
" q_0^s & = -10 + 20p_0 \\\\\n",
" q_1^s & = -15 + 15p_1 \\\\\n",
" q_2^s & = -5 + 10p_2\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"Equilibrium holds when supply equals demand, i.e, $ q_0^d = q_0^s $, $ q_1^d = q_1^s $ and $ q_2^d = q_2^s $.\n",
"\n",
"1. Set up the market as a system of linear equations. \n",
"1. Use matrix algebra to solve for equilibrium prices. Do this using both the `numpy.linalg.solve`\n",
" and `inv(A)` methods. Compare the solutions. "
]
},
{
"cell_type": "markdown",
"id": "31c8c063",
"metadata": {},
"source": [
"## Solution to[ Exercise 8.1](https://intro.quantecon.org/#lin_eqs_ex1)\n",
"\n",
"The generated system would be:\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
" 35p_0 - 5p_1 - 5p_2 = 100 \\\\\n",
" -5p_0 + 25p_1 - 10p_2 = 75 \\\\\n",
" -5p_0 - 5p_1 + 15p_2 = 55\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"In matrix form we will write this as:\n",
"\n",
"$$\n",
"Ap = b\n",
"\\quad \\text{where} \\quad\n",
"A =\n",
"\\begin{bmatrix}\n",
" 35 & -5 & -5 \\\\\n",
" -5 & 25 & -10 \\\\\n",
" -5 & -5 & 15\n",
"\\end{bmatrix}\n",
", \\quad p =\n",
"\\begin{bmatrix}\n",
" p_0 \\\\\n",
" p_1 \\\\\n",
" p_2\n",
"\\end{bmatrix}\n",
"\\quad \\text{and} \\quad\n",
"b = \n",
"\\begin{bmatrix}\n",
" 100 \\\\\n",
" 75 \\\\\n",
" 55\n",
"\\end{bmatrix}\n",
"$$"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "b15f709c",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"import numpy as np\n",
"from numpy.linalg import det\n",
"\n",
"A = np.array([[35, -5, -5], # matrix A\n",
" [-5, 25, -10],\n",
" [-5, -5, 15]])\n",
"\n",
"b = np.array((100, 75, 55)) # column vector b\n",
"b.shape = (3, 1)\n",
"\n",
"det(A) # check if A is nonsingular"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "5930a72a",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"# Using inverse\n",
"from numpy.linalg import det\n",
"\n",
"A_inv = inv(A)\n",
"\n",
"p = A_inv @ b\n",
"p"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "b088d654",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"# Using numpy.linalg.solve\n",
"from numpy.linalg import solve\n",
"p = solve(A, b)\n",
"p"
]
},
{
"cell_type": "markdown",
"id": "344efc61",
"metadata": {},
"source": [
"The solution is given by:\n",
"\\$$ p_0 = 4.6925, \\; p_1 = 7.0625 \\;\\; \\text{and} \\;\\; p_2 = 7.675 $\\$"
]
},
{
"cell_type": "markdown",
"id": "4e400b1b",
"metadata": {},
"source": [
"## Exercise 8.2\n",
"\n",
"Earlier in the lecture we discussed cases where the system of equations given by $ Ax = b $ has no solution.\n",
"\n",
"In this case $ Ax = b $ is called an *inconsistent* system of equations.\n",
"\n",
"When faced with an inconsistent system we try to find the best “approximate” solution.\n",
"\n",
"There are various methods to do this, one such method is the **method of least squares.**\n",
"\n",
"Suppose we have an inconsistent system\n",
"\n",
"\n",
"\n",
"$$\n",
"Ax = b \\tag{8.15}\n",
"$$\n",
"\n",
"where $ A $ is an $ m \\times n $ matrix and $ b $ is an $ m \\times 1 $ column vector.\n",
"\n",
"A **least squares solution** to [(8.15)](#equation-inconsistent) is an $ n \\times 1 $ column vector $ \\hat{x} $ such that, for all other vectors $ x \\in \\mathbb{R}^n $, the distance from $ A\\hat{x} $ to $ b $\n",
"is less than the distance from $ Ax $ to $ b $.\n",
"\n",
"That is,\n",
"\n",
"$$\n",
"\\|A\\hat{x} - b\\| \\leq \\|Ax - b\\|\n",
"$$\n",
"\n",
"It can be shown that, for the system of equations $ Ax = b $, the least squares\n",
"solution $ \\hat{x} $ is\n",
"\n",
"\n",
"\n",
"$$\n",
"\\hat{x} = (A^T A)^{-1} A^T b \\tag{8.16}\n",
"$$\n",
"\n",
"Now consider the general equation of a linear demand curve of a good given by:\n",
"\n",
"$$\n",
"p = m - nq\n",
"$$\n",
"\n",
"where $ p $ is the price of the good and $ q $ is the quantity demanded.\n",
"\n",
"Suppose we are trying to *estimate* the values of $ m $ and $ n $.\n",
"\n",
"We do this by repeatedly observing the price and quantity (for example, each\n",
"month) and then choosing $ m $ and $ n $ to fit the relationship between $ p $ and\n",
"$ q $.\n",
"\n",
"We have the following observations:\n",
"\n",
"|Price|Quantity Demanded|\n",
"|:------------------------------------------------:|:------------------------------------------------:|\n",
"|1|9|\n",
"|3|7|\n",
"|8|3|\n",
"Requiring the demand curve $ p = m - nq $ to pass through all these points leads to the\n",
"following three equations:\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
" 1 = m - 9n \\\\\n",
" 3 = m - 7n \\\\\n",
" 8 = m - 3n\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"Thus we obtain a system of equations $ Ax = b $ where $ A = \\begin{bmatrix} 1 & -9 \\\\ 1 & -7 \\\\ 1 & -3 \\end{bmatrix} $,\n",
"$ x = \\begin{bmatrix} m \\\\ n \\end{bmatrix} $ and $ b = \\begin{bmatrix} 1 \\\\ 3 \\\\ 8 \\end{bmatrix} $.\n",
"\n",
"It can be verified that this system has no solutions.\n",
"\n",
"(The problem is that we have three equations and only two unknowns.)\n",
"\n",
"We will thus try to find the best approximate solution for $ x $.\n",
"\n",
"1. Use [(8.16)](#equation-least-squares) and matrix algebra to find the least squares solution $ \\hat{x} $. \n",
"1. Find the least squares solution using `numpy.linalg.lstsq` and compare the results. "
]
},
{
"cell_type": "markdown",
"id": "97191457",
"metadata": {},
"source": [
"## Solution to[ Exercise 8.2](https://intro.quantecon.org/#lin_eqs_ex2)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "7599a02e",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"import numpy as np\n",
"from numpy.linalg import inv"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "4d3632b4",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"# Using matrix algebra\n",
"A = np.array([[1, -9], # matrix A\n",
" [1, -7],\n",
" [1, -3]])\n",
"\n",
"A_T = np.transpose(A) # transpose of matrix A\n",
"\n",
"b = np.array((1, 3, 8)) # column vector b\n",
"b.shape = (3, 1)\n",
"\n",
"x = inv(A_T @ A) @ A_T @ b\n",
"x"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "8a0c116b",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"# Using numpy.linalg.lstsq\n",
"x, res, _, _ = np.linalg.lstsq(A, b, rcond=None)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "7799e2f6",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"print(f\"x\\u0302 = {x}\")\n",
"print(f\"\\u2016Ax\\u0302 - b\\u2016\\u00B2 = {res[0]}\")"
]
},
{
"cell_type": "markdown",
"id": "91703a2d",
"metadata": {},
"source": [
"Here is a visualization of how the least squares method approximates the equation of a line connecting a set of points.\n",
"\n",
"We can also describe this as “fitting” a line between a set of points."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "d13a309c",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"fig, ax = plt.subplots()\n",
"p = np.array((1, 3, 8))\n",
"q = np.array((9, 7, 3))\n",
"\n",
"a, b = x\n",
"\n",
"ax.plot(q, p, 'o', label='observations', markersize=5)\n",
"ax.plot(q, a - b*q, 'r', label='Fitted line')\n",
"plt.xlabel('quantity demanded')\n",
"plt.ylabel('price')\n",
"plt.legend()\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"id": "35632f35",
"metadata": {},
"source": [
"### Further reading\n",
"\n",
"The documentation of the `numpy.linalg` submodule can be found [here](https://numpy.org/devdocs/reference/routines.linalg.html).\n",
"\n",
"More advanced topics in linear algebra can be found [here](https://python.quantecon.org/linear_algebra.html#id5)."
]
}
],
"metadata": {
"date": 1727242854.424027,
"filename": "linear_equations.md",
"kernelspec": {
"display_name": "Python",
"language": "python3",
"name": "python3"
},
"title": "Linear Equations and Matrix Algebra"
},
"nbformat": 4,
"nbformat_minor": 5
}