#!/usr/bin/env python
# coding: utf-8

# # Finding Schur Form
# 
# Copyright (C) 2026 Andreas Kloeckner
# 
# <details>
# <summary>MIT License</summary>
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
# 
# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.
# 
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
# THE SOFTWARE.
# </details>

# In[1]:


import numpy as np
import numpy.linalg as la
import matplotlib.pyplot as plt

np.set_printoptions(precision=3, linewidth=120)


# Make a nice, well-behaved, diagonalizable matrix with real eigenvalues:

# In[2]:


n = 6
A = np.random.randn(n, n)
U, sigma, VT = la.svd(A)
sigma = 1 + np.arange(n)
X = U + 0.1*np.random.randn(n, n)
A = la.inv(X) @ np.diag(sigma) @ X


# In[11]:


def rayleigh_quotient(mat, x):
    return x @ (mat@x) / (x@x)

def find_an_eigenpair(mat):
    n = len(mat)
    x = np.random.randn(n)
    while True:
        sigma = rayleigh_quotient(mat, x)
        if la.norm(mat@x-sigma*x)/(la.norm(sigma*x)) < 1e-13:
            break
        try:
            x = la.solve(mat - sigma * np.eye(n), x)
        except la.LinAlgError:
            # singular? it's an eigenvalue
            return sigma, x 
        x = x / la.norm(x)

    return rayleigh_quotient(mat, x), x


# In[41]:


lam, x = find_an_eigenpair(A)

print(A@x - lam*x)

del lam
del x


# In[20]:


i = 0
Q = np.eye(n)
R = A.copy()


# Based on an eigenpair, go column-by-column to find Schur form.
# 
# **NOTE:** Please don't do this in real life. It's $O(n^4)$ and numerically not fantastic. But it does (constructively) support the notion that Schur form exists!

# In[26]:


lam, xeig = find_an_eigenpair(R[i:, i:])

eig_onb = np.eye(n)
eig_onb[i:, i:], _ = la.qr(np.hstack((xeig.reshape(-1, 1), np.random.randn(n-i, n-i-1))))
R = eig_onb.T @ R @ eig_onb

i += 1
R.round(3)


# In[ ]: