Eigenvector_in_Max_Plus_Algebra.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Eigenvector in Max-Plus Algebra",
      "provenance": [],
      "authorship_tag": "ABX9TyPTD0jelYTkI/lZ0JpPv4eI",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/msnhdyt/Max-Plus-Algebra/blob/main/Eigenvector_in_Max_Plus_Algebra.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "wKrlatauol6_"
      },
      "source": [
        "import numpy as np\n",
        "\n",
        "# function for calculating A oplus B\n",
        "def oplus(A, B):\n",
        "  if not type(A) is np.ndarray or A.ndim != 2:\n",
        "    raise TypeError(\"the function only receive 2d numpy array\")\n",
        "  result = np.zeros(A.shape)\n",
        "  for i, r in enumerate(A):\n",
        "    for j, c in enumerate(r):\n",
        "      result[i][j] = max(A[i][j], B[i][j])\n",
        "  return result\n",
        "\n",
        "# function for calculating A otimes B\n",
        "def otimes(A, B):\n",
        "  # try:\n",
        "  #   result = np.zeros(A.shape)\n",
        "  #   B = B.T\n",
        "  #   for i, r_a in enumerate(A):\n",
        "  #     k=0\n",
        "  #     for j, r_b in enumerate(B):\n",
        "  #       result[i][k] = max(r_a+r_b)\n",
        "  #       k += 1\n",
        "  #   return result\n",
        "  # except:\n",
        "  #   result = A + B\n",
        "  #   return result\n",
        "  if not type(A) is np.ndarray or A.ndim != 2:\n",
        "    raise TypeError(\"the function only receive 2d numpy array\")\n",
        "\n",
        "  if A.shape == (1,1) or B.shape == (1,1):\n",
        "    result = A + B\n",
        "    return result\n",
        "  else:\n",
        "    result = np.zeros(A.shape)\n",
        "    B = B.T\n",
        "    for i, r_a in enumerate(A):\n",
        "      k=0\n",
        "      for j, r_b in enumerate(B):\n",
        "        result[i][k] = max(r_a+r_b)\n",
        "        k += 1\n",
        "    return result\n",
        "\n",
        "# function for calculating A^n in otimes\n",
        "def pow_otimes(A, n):\n",
        "  if not type(A) is np.ndarray or A.ndim != 2:\n",
        "    raise TypeError(\"the function only receive 2d numpy array\")\n",
        "  result = A\n",
        "  for i in range(n-1):\n",
        "    result = otimes(result, A)\n",
        "  return result\n",
        "\n",
        "# function for calculating trace(A)\n",
        "def trace(A):\n",
        "  if not type(A) is np.ndarray or A.ndim != 2:\n",
        "    raise TypeError(\"the function only receive 2d numpy array\")\n",
        "  return max(A.diagonal())\n",
        "\n",
        "# function for calculating A*\n",
        "def star(A):\n",
        "  if not type(A) is np.ndarray or A.ndim != 2:\n",
        "    raise TypeError(\"the function only receive 2d numpy array\")\n",
        "  \n",
        "  result = np.zeros(A.shape)\n",
        "  # initialize result with E\n",
        "  for i in range(len(A)):\n",
        "    for j in range(len(A)):\n",
        "      if i == j:\n",
        "        result[i][j] = 0\n",
        "      else:\n",
        "        result[i][j] = float('-inf')\n",
        "\n",
        "  for i in range(1,len(A)):\n",
        "    result = oplus(result, pow_otimes(A,i))\n",
        "  \n",
        "  return result\n",
        "\n",
        "# function for calculating A^+\n",
        "def plus(A):\n",
        "  if not type(A) is np.ndarray or A.ndim != 2:\n",
        "    raise TypeError(\"the function only receive 2d numpy array\")\n",
        "  \n",
        "  result = A\n",
        "\n",
        "  for i in range(1,len(A)+1):\n",
        "    result = oplus(result, pow_otimes(A,i))\n",
        "  \n",
        "  return result\n",
        "\n",
        "# function for calculating eigenvalues of A or lambda_max(A)\n",
        "def eigenvalues(A):\n",
        "  if not type(A) is np.ndarray or A.ndim != 2:\n",
        "    raise TypeError(\"the function only receive 2d numpy array\")\n",
        "  result = np.array([[0]])\n",
        "  for i in range(1, len(A)+1):\n",
        "    result = oplus(result, 1/i * np.array([[trace(pow_otimes(A, i))]]))\n",
        "  return result\n",
        "\n",
        "# function for finding eigenvectors of A\n",
        "def eigenvectors(A):\n",
        "  B = otimes(-eigenvalues(A), A)\n",
        "  result = {}\n",
        "  for i, x in enumerate(plus(B).diagonal()):\n",
        "    if x == 0:\n",
        "      result[i] = star(B)[:, i]\n",
        "  return result"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0KWfJBy994IO"
      },
      "source": [
        "# Example Usage"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "WhYfQyU_GL7t",
        "outputId": "3191f952-1031-4b3b-9d4f-7a6f2afa61d1"
      },
      "source": [
        "A = np.array([[-2,3,1], [1,1,float('-inf')], [float('-inf'),2,1]])\n",
        "A"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[ -2.,   3.,   1.],\n",
              "       [  1.,   1., -inf],\n",
              "       [-inf,   2.,   1.]])"
            ]
          },
          "metadata": {},
          "execution_count": 2
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "kYGozQN4-Pwq",
        "outputId": "c2d3af1b-ecbe-411b-fdbe-a3fd75bde06d"
      },
      "source": [
        "eigenvalues(A)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[2.]])"
            ]
          },
          "metadata": {},
          "execution_count": 3
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "H9mOs32fYAxk",
        "outputId": "a33324ad-ed54-436c-8489-c6b868fd61bb"
      },
      "source": [
        "eigenvectors(A)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "{0: array([ 0., -1., -1.]), 1: array([1., 0., 0.])}"
            ]
          },
          "metadata": {},
          "execution_count": 4
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ZGP618uHvtCH",
        "outputId": "5a937ea1-7e64-4bef-ff70-a0e0d489a316"
      },
      "source": [
        "B = otimes(-eigenvalues(A), A)\n",
        "B"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[ -4.,   1.,  -1.],\n",
              "       [ -1.,  -1., -inf],\n",
              "       [-inf,   0.,  -1.]])"
            ]
          },
          "metadata": {},
          "execution_count": 185
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "XHcmLpjSa4Va",
        "outputId": "ea43bed0-29f4-489c-d7c9-0d4b0ebe408d"
      },
      "source": [
        "pow_otimes(B,3)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[-1.,  1., -1.],\n",
              "       [-1., -1., -3.],\n",
              "       [-2.,  0., -2.]])"
            ]
          },
          "metadata": {},
          "execution_count": 183
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "T41TMYXLvVJo",
        "outputId": "e2510c15-fa74-4ed0-ed6a-a1608fa24f61"
      },
      "source": [
        "star(B)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[ 0.,  1., -1.],\n",
              "       [-1.,  0., -2.],\n",
              "       [-1.,  0.,  0.]])"
            ]
          },
          "metadata": {},
          "execution_count": 184
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "I6vFfYQbviK-",
        "outputId": "8e4e95e7-fbfb-4945-82f9-4fd1b1aadf9d"
      },
      "source": [
        "plus(B)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[ 0.,  1., -1.],\n",
              "       [-1.,  0., -2.],\n",
              "       [-1.,  0., -1.]])"
            ]
          },
          "metadata": {},
          "execution_count": 186
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "JfLhWMFsxWEG"
      },
      "source": [
        "C = np.array([[3,0], [8,-1]])\n",
        "D = otimes(-eigenvalues(C),C)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "abGNgIZ71xcL",
        "outputId": "d4764e4c-3349-4c6f-b1db-60dcc1245aeb"
      },
      "source": [
        "star(D)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[ 0., -4.],\n",
              "       [ 4.,  0.]])"
            ]
          },
          "metadata": {},
          "execution_count": 189
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "c20nZSvh1z20",
        "outputId": "6e9acce6-7255-41de-df02-768641a4bcae"
      },
      "source": [
        "plus(D)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[ 0., -4.],\n",
              "       [ 4.,  0.]])"
            ]
          },
          "metadata": {},
          "execution_count": 190
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "HDabpAcv12rH",
        "outputId": "f313ff07-f3d5-4c08-851f-98d79b879ae6"
      },
      "source": [
        "eigenvectors(C)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "{0: array([0., 4.]), 1: array([-4.,  0.])}"
            ]
          },
          "metadata": {},
          "execution_count": 191
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "c_J09Nay131Z"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}