{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is a small Python library implementing an object `Mat2` of matrices over F2, the two-element (boolean) field. Import it as:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from f2linalg import Mat2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Its constructor takes a list of lists of `0` and `1`, representing a matrix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 1  0  1 ]\n",
      "[ 0  1  1 ]\n",
      "[ 1  1  1 ]\n",
      "\n",
      "[ 1  1  1 ]\n",
      "[ 1  1  1 ]\n",
      "[ 1  1  1 ]\n",
      "\n",
      "[ 1  0  1  1 ]\n",
      "[ 0  1  1  1 ]\n",
      "[ 1  1  1  0 ]\n",
      "\n",
      "[ 1 ]\n",
      "[ 0 ]\n",
      "[ 1 ]\n",
      "\n",
      "[ 1 ]\n",
      "[ 1 ]\n",
      "[ 1 ]\n",
      "\n",
      "[ 1  1  1 ]\n",
      "\n",
      "[ 1  0 ]\n",
      "[ 0  1 ]\n",
      "\n",
      "[ 0  0 ]\n",
      "[ 0  0 ]\n",
      "[ 0  0 ]\n"
     ]
    }
   ],
   "source": [
    "# some 3x3 square matrices\n",
    "m = Mat2(\n",
    "    [[1, 0, 1],\n",
    "     [0, 1, 1],\n",
    "     [1, 1, 1]])\n",
    "k = Mat2(\n",
    "    [[1, 1, 1],\n",
    "     [1, 1, 1],\n",
    "     [1, 1, 1]])\n",
    "\n",
    "# a 3x4 rectangular matrix\n",
    "n = Mat2(\n",
    "    [[1, 0, 1, 1],\n",
    "     [0, 1, 1, 1],\n",
    "     [1, 1, 1, 0]])\n",
    "\n",
    "# 3x1 matrices, i.e. column vectors\n",
    "v = Mat2([[1], [0], [1]])\n",
    "v1 = Mat2([[1], [1], [1]])\n",
    "\n",
    "# a 1x3 matrix, i.e. a row vector\n",
    "w = Mat2([[1, 1, 1]])\n",
    "\n",
    "# a 2x2 identity matrix\n",
    "id5 = Mat2.id(2)\n",
    "\n",
    "# a 3x2 all-zero matrix\n",
    "z32 = Mat2.zeros(3, 2)\n",
    "\n",
    "print(m, k, n, v, v1, w, id5, z32, sep='\\n\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`+` is overloaded to perform matrix/vector addition (modulo 2), and `*` to perform F2 matrix multiplication."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 0 ]\n",
      "[ 1 ]\n",
      "[ 0 ]\n",
      "\n",
      "[ 0  0  0 ]\n",
      "[ 0  0  0 ]\n",
      "[ 0  0  0 ]\n",
      "\n",
      "[ 0 ]\n",
      "[ 1 ]\n",
      "[ 0 ]\n",
      "\n",
      "[ 0  0  0 ]\n",
      "[ 0  0  0 ]\n",
      "[ 1  1  1 ]\n",
      "\n",
      "[ 1 ]\n",
      "\n",
      "[ 0 ]\n",
      "[ 1 ]\n",
      "[ 1 ]\n"
     ]
    }
   ],
   "source": [
    "print(\n",
    "    v + v1,\n",
    "    m + m,\n",
    "    m * v,\n",
    "    m * k,\n",
    "    w * m * v,\n",
    "    m * (v + v1),\n",
    "sep='\\n\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`transpose()` returns the transpose:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 1  0  1  1 ]\n",
      "[ 0  1  1  1 ]\n",
      "[ 1  1  1  0 ]\n",
      "\n",
      "[ 1  0  1 ]\n",
      "[ 0  1  1 ]\n",
      "[ 1  1  1 ]\n",
      "[ 1  1  0 ]\n"
     ]
    }
   ],
   "source": [
    "print(n, n.transpose(), sep='\\n\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Almost all non-trivial functionality is implemented using the `gauss` method under the hood. This performs (in-place) reduction to row echelon form and reduced row echelon form (`full_reduce=True`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 1  0  1  1 ]\n",
      "[ 0  1  1  1 ]\n",
      "[ 1  1  1  0 ]\n",
      "\n",
      "[ 1  0  1  1 ]\n",
      "[ 0  1  1  1 ]\n",
      "[ 0  0  1  0 ]\n",
      "\n",
      "[ 1  0  0  1 ]\n",
      "[ 0  1  0  1 ]\n",
      "[ 0  0  1  0 ]\n"
     ]
    }
   ],
   "source": [
    "n_ref = n.copy()\n",
    "n_ref.gauss()\n",
    "\n",
    "n_rref = n.copy()\n",
    "n_rref.gauss(full_reduce=True)\n",
    "\n",
    "print(n, n_ref, n_rref, sep='\\n\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It takes an optional parameter `x` which is can be used to perform Gaussian elimination on an augmented matrix, e.g. to solve linear systems or invert a matrix.\n",
    "\n",
    "For example, we can solve the linear system `m * x = b` as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "system:\n",
      "1*x0 + 0*x1 + 1*x2 = 1\n",
      "0*x0 + 1*x1 + 1*x2 = 0\n",
      "1*x0 + 1*x1 + 1*x2 = 1\n",
      "\n",
      "solution:\n",
      "x0 = 1\n",
      "x1 = 0\n",
      "x2 = 0\n"
     ]
    }
   ],
   "source": [
    "mg = m.copy()\n",
    "b = Mat2([[1], [0], [1]])\n",
    "\n",
    "print('system:')\n",
    "for i in range(m.rows()):\n",
    "    print(' + '.join([f'{m[i,j]}*x{j}' for j in range(m.cols())]) + f' = {b[i,0]}')\n",
    "\n",
    "mg.gauss(x=b, full_reduce=True) # this results in `b` getting transformed to the solution `x`\n",
    "print('\\nsolution:', *[f'x{i} = {b[i,0]}' for i in range(m.rows())], sep='\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "...and invert a matrix as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 1  0  1 ]\n",
      "[ 0  1  1 ]\n",
      "[ 1  1  1 ]\n",
      "\n",
      "[ 0  1  1 ]\n",
      "[ 1  0  1 ]\n",
      "[ 1  1  1 ]\n",
      "\n",
      "[ 1  0  0 ]\n",
      "[ 0  1  0 ]\n",
      "[ 0  0  1 ]\n",
      "\n",
      "[ 1  0  0 ]\n",
      "[ 0  1  0 ]\n",
      "[ 0  0  1 ]\n"
     ]
    }
   ],
   "source": [
    "mg = m.copy()\n",
    "mi = Mat2.id(3)\n",
    "mg.gauss(x=mi, full_reduce=True)\n",
    "print(\n",
    "    m,\n",
    "    mi,\n",
    "    m * mi,\n",
    "    mi * m,\n",
    "    sep='\\n\\n'\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can also get these via convenience methods `solve()` and `inverse()`, which do not change `m` or `b`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x =\n",
      "[ 1 ]\n",
      "[ 0 ]\n",
      "[ 0 ]\n",
      "\n",
      "mi =\n",
      "[ 0  1  1 ]\n",
      "[ 1  0  1 ]\n",
      "[ 1  1  1 ]\n"
     ]
    }
   ],
   "source": [
    "b = Mat2([[1], [0], [1]])\n",
    "print(f'x =\\n{m.solve(b)}', f'mi =\\n{m.inverse()}', sep='\\n\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can get the rank of a matrix with `rank`. Any rank-R matrix of size MxN can always be factored as `k = k0 * k1` where `k0` is an MxR matrix and `k1` is an RxM matrix, using the `factor` method."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "rank(k) = 1\n",
      "\n",
      "[ 1  1  1 ]\n",
      "[ 1  1  1 ]\n",
      "[ 1  1  1 ]\n",
      "\n",
      "[ 1 ]\n",
      "[ 1 ]\n",
      "[ 1 ]\n",
      "\n",
      "[ 1  1  1 ]\n"
     ]
    }
   ],
   "source": [
    "k0, k1 = k.factor()\n",
    "print(f'rank(k) = {k.rank()}', k0 * k1, k0, k1, sep='\\n\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `nullspace()` method returns a spanning set for the nullspace (a.k.a. kernel) of the matrix. That is, it is a spanning set of solutions for the associated homogeneous system of equations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[ 1 ]\n",
       " [ 1 ]\n",
       " [ 0 ],\n",
       " [ 1 ]\n",
       " [ 0 ]\n",
       " [ 1 ]]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "k.nullspace()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It returns an empty list if the matrix is invertible, meaning the only vector in the nullspace is 0:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m.nullspace()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.12.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}