t4_linear_independence.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Table of Contents](table_of_contents.ipynb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Topic 4.  Linear Independence\n",
    "\n",
    "Author: Zheng Sun (zsun2@byu.edu)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##  Introduction\n",
    "\n",
    "A subset of a vector space is **linearly independent** if none of its elements can be written as a *linear combination* of the others.\n",
    "\n",
    "Together with *linear combination*, *spanning*, and *basis*, **linear independence** is a fundamental concept in *vector spaces* theory."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Explanation of the theory\n",
    "\n",
    "### Definition\n",
    "\n",
    "Let $S$ be a vector space, and let $T$ be a subset of $S$. The set $T$ is **linearly independent** if for each finite nonempty subset of $T$ (say $\\{\\mathbf{p}_1, \\mathbf{p}_2, \\cdots, \\mathbf{p}_m\\}$) the only set of scalars satisfying the equation\n",
    "\n",
    "$$c_1\\mathbf{p}_1 + c_2\\mathbf{p}_2 + \\cdots + c_m\\mathbf{p}_m = 0$$\n",
    "\n",
    "is the trivial solution $c_1 = c_2 = \\cdots = c_m = 0$.\n",
    "\n",
    "\n",
    "The set of vectors $\\{\\mathbf{p}_1, \\mathbf{p}_2, \\cdots, \\mathbf{p}_m\\}$ is said to be **linearly dependent** if there exists a set of scalar coefficients $\\{c_1, c_2, \\cdots, c_m\\}$ which are not all zero, such that $c_1\\mathbf{p}_1 + c_2\\mathbf{p}_2 + \\cdots + c_m\\mathbf{p}_m = 0$.\n",
    "\n",
    "Note that linear dependence/independence is a concept that applies to a collection of vectors, not to a single vector, or to one vector in the presence of some others.\n",
    "\n",
    "### Matrix notation\n",
    "\n",
    "The set of vectors $\\{\\mathbf{p}_1, \\mathbf{p}_2, \\cdots, \\mathbf{p}_m\\}$ is linearly independent if and only if the matrix $\\mathbf{A}$ with columns $\\mathbf{p}_1, \\mathbf{p}_2, \\cdots, \\mathbf{p}_m$ has a pivot in every column, if and only if $\\mathbf{Ac} = 0$ has only the trivial solution ($\\mathbf{c} = [c_1, c_2, \\cdots, c_m]^T$).\n",
    "\n",
    "Solving the matrix equation $\\mathbf{Ac} = 0$ will either verify that the columns $\\mathbf{p}_1, \\mathbf{p}_2, \\cdots, \\mathbf{p}_m$ are linearly independent, or produce a linear dependence relation by substituting any nonzero values for the free variables.\n",
    "\n",
    "### Other facts\n",
    "\n",
    "- Any set containing the zero vector is linearly dependent.\n",
    "\n",
    "- Two vectors are linearly dependent if and only if they are collinear.\n",
    "\n",
    "- A set of vectors $\\{\\mathbf{p}_1, \\mathbf{p}_2, \\cdots, \\mathbf{p}_m\\}$ is linearly independent if and only if the rank of the matrix $\\mathbf{A}$ with columns $\\mathbf{p}_1, \\mathbf{p}_2, \\cdots, \\mathbf{p}_m$ is $m$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Simple Numerical Examples"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import modules for linear algebra\n",
    "import numpy as np\n",
    "import sympy\n",
    "sympy.init_printing()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example 1\n",
    "\n",
    "Is the set of vectors $\\begin{Bmatrix}\\begin{pmatrix}1\\\\2\\end{pmatrix}, \\begin{pmatrix}3\\\\4\\end{pmatrix}\\end{Bmatrix}$ linearly independent?\n",
    "\n",
    "Firstly, we form a matrix equation:\n",
    "\n",
    "$$\\begin{bmatrix}1&3\\\\2&4\\end{bmatrix}\\begin{bmatrix}c_1\\\\c_2\\end{bmatrix} = \\begin{bmatrix}0\\\\0\\end{bmatrix}$$\n",
    "\n",
    "It implies that $\\begin{cases}{c_1 + 3c_2 = 0\\\\2c_1 + 4c_2 = 0}\\end{cases}$.\n",
    "\n",
    "As this simultaneous equation has no nonzero solution, $\\begin{Bmatrix}\\begin{pmatrix}1\\\\2\\end{pmatrix}, \\begin{pmatrix}3\\\\4\\end{pmatrix}\\end{Bmatrix}$ is linearly independent."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example 2\n",
    "\n",
    "Is the set of vectors $\\begin{Bmatrix}\\begin{pmatrix}1\\\\2\\\\3\\end{pmatrix}, \\begin{pmatrix}2\\\\4\\\\6\\end{pmatrix}\\end{Bmatrix}$ linearly independent?\n",
    "\n",
    "The matrix equation is:\n",
    "\n",
    "$$\\begin{bmatrix}1&2\\\\2&4\\\\3&6\\end{bmatrix}\\begin{bmatrix}c_1\\\\c_2\\end{bmatrix} = \\begin{bmatrix}0\\\\0\\end{bmatrix}$$\n",
    "\n",
    "We can try solving this equation, like what we do in last example. Also, we can use *Gaussian elimination* (also known as *row reduction*) to find the rank of matrix $\\begin{bmatrix}1&2\\\\2&4\\\\3&6\\end{bmatrix}$ ($\\mathbf{A}$).\n",
    "\n",
    "For simplicity, we do not implement *Gaussian elimination* from scratch here, just use an inner method `rref()` in SymPy `Matrix` object. `rref()` returns a tuple of two elements, the first is the reduced row echelon form (RREF), and the second is a tuple of indices of the pivot columns."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Rank of A = 1\n",
      "RREF of A = \n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAADkAAABLCAMAAAD9LN99AAAAOVBMVEX///8AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACXHtMAAAAEnRSTlMAMquJZkQiEEAw3ZnNdrvvVHxhCJaFAAAACXBIWXMAAA7EAAAOxAGVKw4bAAABpUlEQVRYCe2Y25LEEBiEBYldclrv/7CLPybaIRNTe7NVcTMp7UOaaSlssKFwdrdoAhgbrJCujHdB5ltLbj053YbOhjIjB61OMX+ajJnX4agFUnEz2zY5eSeEPd4KSCcsFyQPnW4bDdpDbqFXfrjSQ3LtR+OW3rSHpFlq56kv3eRglw9JbQjsHtNEsJeUL7CT3IWb6kR7tcuhwYNsoV3WQ07auEKrmq8KXzer+WH74eH5M9PfcqaafMyz3bunh3wc+uM9JMRiLgI/lXH3zTtjSjdRkIGUIRbF2lhKlIFcw0G4t2IeZSBtSJnRujnXCsopqaIkaxzL5JScbMiZVxZnfCZXydBBxrnMix2TnJKKpDHmf8Zmsie/7Dc1ovfcrx2K8k962q9hJWVzVUBOZ8tkOI7NEYvZZF3Cggwk0373bfEbokBBRlKJZeFNkIGMZDHKRcVDXpgTpMehTofSKK6gqYzeQhSXJMhAYhQXJMpAYhQXJMpAxrx9ktq5FoO84lCM4sJbDHIgn6Qu3Mq/4ysNmlXgbbNVTfiP5Kc3ESrcLPTeREjJfgFiCh+x0HGBPAAAAABJRU5ErkJggg==\n",
      "text/latex": [
       "$$\\left[\\begin{matrix}1 & 2\\\\0 & 0\\\\0 & 0\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡1  2⎤\n",
       "⎢    ⎥\n",
       "⎢0  0⎥\n",
       "⎢    ⎥\n",
       "⎣0  0⎦"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "A = sympy.Matrix([[1,2], [2,4], [3,6]])\n",
    "rref, idx = A.rref()\n",
    "\n",
    "print(\"Rank of A = {}\".format(len(idx)))\n",
    "print(\"RREF of A = \")\n",
    "display(rref)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As the result shows, the rank of $\\mathbf{A}$ is 1, less than 2, the number of columns. Therefore, $\\begin{Bmatrix}\\begin{pmatrix}1\\\\2\\\\3\\end{pmatrix}, \\begin{pmatrix}2\\\\4\\\\6\\end{pmatrix}\\end{Bmatrix}$ is linearly dependent."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example 3\n",
    "\n",
    "Is the set of vectors $\\begin{Bmatrix}\\begin{pmatrix}1\\\\1\\\\-2\\end{pmatrix}, \\begin{pmatrix}1\\\\-1\\\\2\\end{pmatrix}, \\begin{pmatrix}3\\\\1\\\\4\\end{pmatrix}\\end{Bmatrix}$ linearly independent?\n",
    "\n",
    "The matrix $\\mathbf{A}$ is $\\begin{bmatrix}1&1&3\\\\1&-1&1\\\\-2&2&4\\end{bmatrix}$. Just do *Gaussian elimination* on $\\mathbf{A}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Rank of A = 3\n",
      "RREF of A = \n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAFgAAABLCAMAAADDCbAzAAAAOVBMVEX///8AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACXHtMAAAAEnRSTlMAMquJZkQiEEAw3ZnNdrvvVHxhCJaFAAAACXBIWXMAAA7EAAAOxAGVKw4bAAACN0lEQVRYCe2Z0XKDIBBFUUlsNWrK/39sAQvuRZYdUpuZzuBDQ7zZ47qhk9NGdcYfvbromHaeUp0ZtD1uF3GVg+neOPD9KubB0QjupvHIzqthWOZCEzSm4LGfH6YEfjyVGieWDDEF2w6XElhP7h6G9Xwn/gzGNeDV75snd22Ma8Bmdp3djB1I7sC4AjyGSp3DqiSuAN/N4IidWbLgJH4F7PkneATvcQV43Du+MR0ncQVY7TN+lt+8ENeAV7+DNbvdIK4B680Ndn6cxrufwLgGrCb3K711DBhjAPfrZqY+v5scbRyWpWe5GAOYa+WV8w0cp9ZG0UYRJxAXb9oV1DjitemiLDS0HDoG46C8fS0JDZRTMBrHGWzPlIQGyykYjaMajOUUHLyBERJ3pVLHWE7AiXHUdpyUE3AUA/4jpNRxUp4D54XE30FhFBF8EpbEOOpH4YnBZ1zHH+bTUwQhca8pdJz4zBf5U0EQEgmM5WTGCo3D30T6o9QxllMwGkfK9M9LYCwHsCAkShAaKAdwtskXTzZwHFwbRRtFnEBcvGlXUOOI1yYLKSc+Ax2DcRBeWJZz9BkKRuMItONRyuEDhoLROA5gWEk5C0bjCLjjUco5cGIcB/BnJeX2ZeQDhowiigEjLFIugxlhiWAmZ8GSsEg5C06Mw74uOWShyc9YoXEkVPtUyrk3TxQWNJLzhVkwGkemUPgPCw8G48iAhRx8huzjDOkXpxo4Du+/juKPvmAZ/TciF3/BorX6BphxJ5MVW0+5AAAAAElFTkSuQmCC\n",
      "text/latex": [
       "$$\\left[\\begin{matrix}1 & 0 & 0\\\\0 & 1 & 0\\\\0 & 0 & 1\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡1  0  0⎤\n",
       "⎢       ⎥\n",
       "⎢0  1  0⎥\n",
       "⎢       ⎥\n",
       "⎣0  0  1⎦"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "A = sympy.Matrix([[1,1,3], [1,-1,1], [-2,2,4]])\n",
    "rref, idx = A.rref()\n",
    "\n",
    "print(\"Rank of A = {}\".format(len(idx)))\n",
    "print(\"RREF of A = \")\n",
    "display(rref)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It shows that, the rank of $\\mathbf{A}$ is 3, equal to the number of columns. Therefore, $\\begin{Bmatrix}\\begin{pmatrix}1\\\\1\\\\-2\\end{pmatrix}, \\begin{pmatrix}1\\\\-1\\\\2\\end{pmatrix}, \\begin{pmatrix}3\\\\1\\\\4\\end{pmatrix}\\end{Bmatrix}$ is linearly independent."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## An Engineering Application\n",
    "\n",
    "Let us look at a chemical engineering application.\n",
    "\n",
    "> The following reactions are proposed in the hydrogenation of bromine:\n",
    "> \n",
    "> $$\\begin{align*}H_2 + Br_2 &\\rightleftharpoons 2HBr\\\\\n",
    "Br_2 &\\rightleftharpoons 2Br\\\\\n",
    "Br + H_2 &\\rightleftharpoons HBr + H\\\\\n",
    "H + Br_2 &\\rightleftharpoons HBr + Br\\\\\n",
    "H + HBr &\\rightleftharpoons H_2 + Br\\\\\n",
    "2Br &\\rightleftharpoons Br_2\\end{align*}$$\n",
    "> \n",
    "> We can find out a set of independent reactions from these reactions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Firstly, we create a species vector $\\mathbf{c} = [H_2, H, Br_2, Br, HBr]^T$, and a stoichiometric coefficients matrix $\\mathbf{A}$. Each row in $\\mathbf{A}$ represents a reaction with negative coefficients for reactants, and positive coefficients for products. A coefficient of zero denotes species not participating in the reaction. Then, 6 given reactions can be represented by $\\mathbf{A}*\\mathbf{c}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A = \n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAOgAAACWCAMAAADjXzT7AAAAOVBMVEX///8AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACXHtMAAAAEnRSTlMAMquJZkQiEEAwzd2ZdrvvVHw66LwlAAAACXBIWXMAAA7EAAAOxAGVKw4bAAAG1UlEQVR4Ae2d62KrOAyEHZImuyFpe3j/h11uBtmMYERhqTnmR2OwLOazIJdp6rpL1W6FO+lWdnzOXarrrd4+TsrpGrhbUTWg97Myjly3BdBL+RiD1db1+n6tmSwuu7Olv79ez89LrHUW9FG8nhUB+vx27lFaSdnszpb+3jzXXKv4RpwFrUe8CdBb2Uzf9bP5aduY7M6Yvmgr8/UVKdkC9LN9vv4mpiQ6OTWNzpj+q9VRxM87W4BWrwbgo6ovYONGVdSYvmivr6KK7tINQB9eyc2Iyd0Y69KX9ZNssG0Aeq+uTcpL9Q4yMztMRVeln4rZErTlZfiGGBOoJX3Z3k3DeepGAPp4luPWXeOElEdX0Y+liq7L7tj0kuo14QxBZWzfJkBdd49+7/tkZEl/m3JuAvrZvoLednt5sab/bi7ye/T+Jbh0V1b01r44v55g+MIh5npx1vSX9mZ+R+/otgB1ZfMW8Ct64VpgbLspUGP6e/mqt+7VVGiYBy0+v6qyWHzZeFzf78LOSWZ3tvTP7tNnfH3Ng4oZSb2ZQVOvYKw/VzSekdT3c0VTr2CsP1c0npHU93NFU69grF+pqM0yNjrMowbOwMaO9JglbkHxGNRmGRsdZq+LNbAVR9qnmTxi8RDUaBkbw4Uy6mOa4kiLNEFTUQNBjZaxMVzIokAVR1qkCZqKGgjqjVrSkTaGC1kUqOJIizRBU1GDQI2WsTFcqqJAuwETR1rmEW1NDQI1WsbGcCGK+91LO2DqSMs8oq2pmQXlLOMhNRcuRBlAp460zCPampoG9J/qXxFZ+1ykI90PYsNXGtjtWYAjHUgedzQ1fwCo1ZHe2cCuIZAjPbKFLUVNAzr5DoPRkTaGC13kkxF0pEWaoKmoQfeo1TK2OsyjLg4UO9JjlrClqIGgRsvYGj4Ko0AVR3rMErWwnY5BbZax0WEedJEGtuJID2niBhaPQeOxJ9jPoCcoYoCQKxpMxwl2ckVPUMQAoano4xb9GjyIOMnOvf661+S97knYAox8jwbTcYKdpYpyFrMjw/yEQYvZd848kqdBYbOgpMVMho0A2GIe+3GLPI0SNgtan5D6IEWHdQSKxYzxgqM/UHMEqGIxB0h4JzFQxWLGbMHRtEA1izlAwjtpgQ7O6+JX7ya0iYLuZnij+WiejAYDe73FjFJP6tEf0CzmOH5bNdDXFackCciwLrFiMYuzak3yNCjskJcX61eqB25EMHSODRR2BKhiMY9C1RYiAMEo7AjQnQ1v/D5tHpS0mMmwYe6xxTx0aw3yNDhsHlQ7ZYLHM2iCRZuVnCs6Oz0JduaKJli0WclNRbOBPTtFiXXmezSxgi3KVSq6s8PsZSGn2ffJRzauH4PCMeiuDrMnUJxm3z08snH9ACUcgu7uMHsI9MHR98lHNq4fg8Ih6O4Os4dAinyffGTjrKC7O8weggVg44yg+zvMvwR0f4f5t4Hu5jAfBDoY2P35d3KY1xvS7C8v5+YPGti7O8xzinyffNzpycgpX2KWp1baGyhCmTdIC19Hd3eYPQwLwMb1eVE4BN3dYf41oPs6zB4TO82+d3xk4/oROBxXdDzJaVoZ9DSl7EFyRXNFE52B5tKN3+smijIvG77XnR+SZm9+Mkqzbrrqv76iyAPWp2voIYdZ/XEy7SCjb8hhsKKKBxzniffpYTZ/nE4b6omGQdB6BPpIFyaCe9Qwuz9OpZ0KksOOALX741LxlEc9IocdAWr3x6ViFWvaIYcdALrCH5eKpzzqETnsANAV/rhUrGJNO+SwI0F5f1wqnvKoR+SwBhRtMgb1N8dWOtKsPy5Ou5Ea9NeGTGqhxDepYXZ/nErrNYyPctgBl+4Kf1wqHjkWW3LYEaB2f1wqXsQbA+SwI0Dt/rhUPHIstuQwDIo94MXE7DCjP86mjfSFwzBoNOQMuxn0DFWUDLmicjbO0M4VPUMVJUOuqJyNM7RzRc9QRcmgVNToMBvD6wV3qP8NKYXWbXYtbKgGg9ocZusa2JG1HOGou+xa2Fg8BDU6zMbwhkR+gFLJog5yLWxFDQQ1OszG8LWg5FrYihoIanSYjeFrQcm1sBU1CNToMBvD2wtyzaXbXclLa2FrahCo0WE2hv8MdHEtbE3NLCjnMA+pufCfgS6uha2pQaBGh9kYToMCf9wtr4WtqUGg/8Ma2CvvUWYtbMUeh6DGb2Abw5uSrgOl1sJW1EBQo8NsDF8Nyq2FraiBoFaHGa863d6Myo81FWXXwsZqMKjRYTaGu9BaVuZicphdCxurwaCTk6R/IIOmX8OQIFc0nI/09/6yirb/VrdIv2yYoOz+a3CzhEi7feCw9I92eDf3H8nHbY2XvGTnAAAAAElFTkSuQmCC\n",
      "text/latex": [
       "$$\\left[\\begin{matrix}-1 & 0 & -1 & 0 & 2\\\\0 & 0 & -1 & 2 & 0\\\\-1 & 1 & 0 & -1 & 1\\\\0 & -1 & -1 & 1 & 1\\\\1 & -1 & 0 & 1 & -1\\\\0 & 0 & 1 & -2 & 0\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡-1  0   -1  0   2 ⎤\n",
       "⎢                  ⎥\n",
       "⎢0   0   -1  2   0 ⎥\n",
       "⎢                  ⎥\n",
       "⎢-1  1   0   -1  1 ⎥\n",
       "⎢                  ⎥\n",
       "⎢0   -1  -1  1   1 ⎥\n",
       "⎢                  ⎥\n",
       "⎢1   -1  0   1   -1⎥\n",
       "⎢                  ⎥\n",
       "⎣0   0   1   -2  0 ⎦"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "labels = ['H2', 'H', 'Br2', 'Br', 'HBr']\n",
    "\n",
    "#    {H2, H, Br2, Br, HBr}\n",
    "A = [[-1,  0, -1,  0,  2],  # H2 + Br2 = 2HBr\n",
    "     [ 0,  0, -1,  2,  0],  # Br2 = 2Br\n",
    "     [-1,  1,  0, -1,  1],  # Br + H2 = HBr + H\n",
    "     [ 0, -1, -1,  1,  1],  # H + Br2 = HBr + Br\n",
    "     [ 1, -1,  0,  1,  -1], # H + HBr = H2 + Br\n",
    "     [ 0,  0,  1, -2,  0]]  # 2Br = Br2\n",
    "\n",
    "# convert A to Matrix object\n",
    "A = sympy.Matrix(A)\n",
    "\n",
    "print(\"A = \")\n",
    "display(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As we know, there are three types of elementary row operations for *Gaussian elimination*:\n",
    "\n",
    "* Swapping two rows\n",
    "* Multiplying a row by a nonzero number\n",
    "* Adding a multiple of one row to another row\n",
    "\n",
    "For a stoichiometric coefficients matrix, these operations are all reasonable. Let us do *Gaussian elimination* on $\\mathbf{A}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "RREF of A = \n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAALcAAACWCAMAAACrQOk+AAAAOVBMVEX///8AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACXHtMAAAAEnRSTlMAMquJZkQiEEAw3ZnNdrvvVHxhCJaFAAAACXBIWXMAAA7EAAAOxAGVKw4bAAAGrklEQVR4Ae1dbXviOAwMkMIdL203///HXhLsiZSMLblmeaDnfNgo0Wg0VQxlp95ttxvmY9+9x3G+y+263XDox+PjPWR3k9Z+P0y6j28ieZHZr3TvzqcluYkOh9sl8zUa6Uh3vFyun7t45T6rMqX7tL9ch4zu63fXnc5J4UY6CjxOL6TDULosdZnSPfLdMrr789T68Dn9SQ4jjYr9PJmvL9zwBbqsRPfn/I7znfrKjDTUfc0E+9IXlS4r0T1cpt4fw7ha2GGkUbKfH9t+KFzhuqxA9ykK6yFBBkZaQqf4PL4h/OCIZQW6j8NharQbbrSfkV7VpFhWsPUlyn6ie5a/Zuygm6dX+PO85lY37UuUFeg+3ef9kZi3kdaaLrbs0/W8HOG1sJQV6O7u6/s7/7pMpqXw3pYt4TEWZSW6P+d37j75PphPx+bj+XtaSsfk9y+BVKEsK9Hdz98qLldFtlwY6QW4m18Bt8w35gUrIlVWors7T9/nv5Lvu0Y6SjieL+NxfzuO9xxnXaZ17z+/hvOev8+N1KfD7bZPyrbSUdv1/vk59dgibH3WZVr3Gvu61033c59Nm3ebt2cCbZ14pvQ4TJv342bpYfol87acmypbaJljnmbBrSJRpuedd24qbaEowqKJuNVZlyndtnNTYQtJGTkaiVvFokzptp0bUbni7Dq7GiU5GoC2gShTuqNBkjB2RiJRuaG1q1GSowFoG4gyqdvh3IjKNa2jGiUZGmBIIMqkbjggyb/w5ObtqIYUIQD3HIEoo7rTzo2oXPeB7nQ1SjI0wJBAlE26/xn+nUEO50ZUrnkd1SjJ0ABDfB9R9kfotoydkVJUokEMDFsowqZzjkbiVrEom3Tj5zuGsWM0tKshQwjAPUcgyuT67mznRlRu+tjVKMnRALQNRJnSbRk7xgN2+j6jHiFgqy59R5Rp3YaxU2cLQY9BA9wqUGVa9wr5wpdN93MfTpt3m7dnAu+8Tk596Y8sPBP5u5jj+MNffD75u60eyv7O6+QXzNvwfYx0J4wZx6pQG3gyeNZVr5O879Pl09qYyegIKb2BJ42nXZVuw/cx0mNn8UEzrSNm9AaeeHdz5l2VbsO5MdJjxyLdegPPRm+8wbsq3YZzY6RLdesNPFHm5sy7St2Gc2Okp4ZF874rjBt4NnrDjURXqRsOCPd9jPTUp1w3NvCkdCe6Ut3cuQEDT/9MNzbwmLp110m30/dxGDvZeRMjp1s28KR0J7oq/8Rwboz02DmrmygTG3hI9n6Ld5XrpDOcGyNdrltu4Enq5l2VbsO5MdLFutUGnqRu3lXptnwf09gpWid6A09SNxeldRu+j5FWxkxaR8zoDTzx7vZMu2rd26JXvdN0P/fJtHm3eXsm8M7rpPk+nif8GMw7r5P/ve/DDBq2LLy4UMvgep1Qi2XpXJcGj0EDXAgoXOnmFgt46tJeGuBCwLsq3dxiAVFd2ksDXAh4V6WbWywgqkt7aYALAe8qdScslkhUl44snUEDXAgScKkbBsmPfB+jGnq8uFCQgFPd2mKJHcHwo3RkKfz3YCn4pPsxvk/CoIHeGHhxAZ+AP9D34QZNlLucvbhQweFynVT6PtygWfTGyIsLeA5XurnFEvtZ24GMai8NcCHgtEo3t1gWIsP3MdLg8eJCAYVr3dRiQT/rH3IZ1eDx4kIBhWvdoH75oOl+7iNq827z9kxgWifx84kH/yoY9fnkVUQ5dLTXpWNID4T8knkzi0VMqS4NIoMGuBAwuJ43tVgWmro0eAwa4EJA4Uo3t1jAU5f20gAXAt5V6eYWC4jq0l4a4ELAuyrd3GIBUV3aSwNcCHhXqTthsUSiunRkab4P9sfWGTtGNebtxYWCBHxaJ/FIWCyPSUeWcZ3MflfqvwkCLgQZOH5Owi0WMNWlvTTAhYB3la/L5vusZ6auuZGjIPKCw9W8m+8jB7aJqZGzQeEGhet5A/vyQdP93EfU5t3m7ZlAWyeeKT0O0+b9uFl6mH7JvJnFIr78ujSIDBrgQsDget7UYllo6tLgMWiACwGFK93cYgFPXdpLA1wIeFelm1ssIKpLe2mACwHvqnRziwVEdWkvDXAh4F2l7jpjx6iGHC8uFCTgUjesirbfB1NeAkyHbxtagPcoAZfzzlgsE0ddGnoMGuBCkIBL3db/78MdGDQy0sW4UMBplW6+tQYN69JeGuBCwLsq3dxiAVFd2ksDXAh4V6W7+T7roalrauQohLqgcD1vhX/pi6b7uY+nzbvN2zOB+zp5z98vdZp/Y9N7/X6pvu/+A05CcOe/19leAAAAAElFTkSuQmCC\n",
      "text/latex": [
       "$$\\left[\\begin{matrix}1 & 0 & 0 & 2 & -2\\\\0 & 1 & 0 & 1 & -1\\\\0 & 0 & 1 & -2 & 0\\\\0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0\\\\0 & 0 & 0 & 0 & 0\\end{matrix}\\right]$$"
      ],
      "text/plain": [
       "⎡1  0  0  2   -2⎤\n",
       "⎢               ⎥\n",
       "⎢0  1  0  1   -1⎥\n",
       "⎢               ⎥\n",
       "⎢0  0  1  -2  0 ⎥\n",
       "⎢               ⎥\n",
       "⎢0  0  0  0   0 ⎥\n",
       "⎢               ⎥\n",
       "⎢0  0  0  0   0 ⎥\n",
       "⎢               ⎥\n",
       "⎣0  0  0  0   0 ⎦"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Put A into RREF\n",
    "rref, idx = A.rref()\n",
    "\n",
    "print(\"RREF of A = \")\n",
    "display(rref)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The RREF matrix $\\mathbf{A}_{RREF}$ shows that there are only 3 independent columns. The independent reactions are defined by $\\mathbf{A}_{RREF}*\\mathbf{c}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 = +1H2 +2Br -2HBr \n",
      "0 = +1H +1Br -1HBr \n",
      "0 = +1Br2 -2Br \n"
     ]
    }
   ],
   "source": [
    "# Find out independent reactions\n",
    "for row in rref.tolist():\n",
    "    \n",
    "    s = \"0 = \"\n",
    "    for coeff, species in zip(row, labels):\n",
    "        if coeff != 0:\n",
    "            s += \"{0:+d}{1} \".format(int(coeff), species)\n",
    "    \n",
    "    if len(s) != 4:\n",
    "        print(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is done! But the answer is not unique, the order of rows and elementary row operations can change it."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References\n",
    "\n",
    "1. Moon, Todd K., and Wynn C. Stirling. Mathematical methods and algorithms for signal processing. No. 621.39: 51 MON. 2000.\n",
    "\n",
    "2. https://en.wikipedia.org/wiki/Linear_independence\n",
    "\n",
    "3. https://en.wikipedia.org/wiki/Gaussian_elimination\n",
    "\n",
    "4. https://docs.sympy.org/latest/tutorial/index.html\n",
    "\n",
    "5. https://textbooks.math.gatech.edu/ila/linear-independence.html\n",
    "\n",
    "6. http://kitchingroup.cheme.cmu.edu/blog/2013/03/01/Determining-linear-independence-of-a-set-of-vectors/\n",
    "\n",
    "7. http://immersivemath.com/ila/ch05_gausselim/ch05.html"
   ]
  }
 ],
 "metadata": {
  "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.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}