这个题目往回看的时候很有趣 简单来说就是要证明如果一个语言能被单带图灵机在$o(nlgn)$时间内被识别, 那么这个语言就是正则的

https://math.stackexchange.com/questions/84040/does-dtimeon-regular?utm_medium=organic&utm_source=google_rich_qa&utm_campaign=google_rich_qa

@bintou 感觉应该分解不唯一吧, 乘回去都是一样的诶

@bintou 已经是矩阵的形式打印出来了, 每一列是一个列向量

import numpy as np
import math

# Given a matrix and its transposed
matrix = np.array([[2, 2], [1, 1]])
matrix_transposed = np.matrix.transpose(matrix)

# Generate (A^T)A and A(A^T)
left_symmetric_matrix = np.matmul(matrix, matrix_transposed)
right_symmetric_matrix = np.matmul(matrix_transposed, matrix)

left_singular_values, left_singular_vectors = np.linalg.eig(
    left_symmetric_matrix)
right_singular_values, right_singular_vectors \
    = np.linalg.eig(right_symmetric_matrix)


# Sort the eigenvalues
U = np.array([ele for _, ele in sorted(
    zip(left_singular_values, left_singular_vectors), reverse=True)])

# Construct a diagonal
Sigma = np.zeros(matrix.shape)
np.fill_diagonal(Sigma, [math.sqrt(abs(val)) for val in left_singular_values])

# V^T
VT = np.array([ele for _, ele in
               sorted(zip(right_singular_values, right_singular_vectors), reverse=True)])
VT = np.matrix.transpose(VT)

print("U=", '\n', U, end='\n\n')
print("Sigma=", '\n', Sigma, end='\n\n')
print("V^T=", '\n', VT, end='\n\n')

print("Back to A=", '\n', np.matmul(np.matmul(U, Sigma), VT))

这个加了一条将分解出来的矩阵乘回去的语句

@bintou ?

@bintou sudo pip3 install numpy

@bintou 要用py3跑

写了一下, 效率很低, 数据样本是从GSLA扒下来的, 有空继续改进

import numpy as np
import math

# Given a matrix and its transposed
matrix = np.array([[2, 2], [1, 1]])
matrix_transposed = np.matrix.transpose(matrix)

# Generate (A^T)A and A(A^T)
left_symmetric_matrix = np.matmul(matrix, matrix_transposed)
right_symmetric_matrix = np.matmul(matrix_transposed, matrix)

left_singular_values, left_singular_vectors = np.linalg.eig(
    left_symmetric_matrix)
right_singular_values, right_singular_vectors \
    = np.linalg.eig(right_symmetric_matrix)


# Sort the eigenvalues
U = np.array([ele for _, ele in sorted(
    zip(left_singular_values, left_singular_vectors), reverse=True)])

# Construct a diagonal
Sigma = np.zeros(matrix.shape)
np.fill_diagonal(Sigma, [math.sqrt(abs(val)) for val in left_singular_values])

# V^T
VT = np.array([ele for _, ele in
               sorted(zip(right_singular_values, right_singular_vectors), reverse=True)])
VT = np.matrix.transpose(VT)

print("U=", '\n', U, end='\n\n')
print("Sigma=", '\n', Sigma, end='\n\n')
print("V^T=", '\n', VT, end='\n\n')

@bintou

@bintou 收到

老师有没有书单 @bintou

@bintou 想到一个$\Theta(mlgn)$ $m$是行数(不知道有没有算错)
首先找中间列的最大元素 然后如果他是比左边同行的大就马上递归找左边 否则右边. 直到剩下一列停止递归(但是要先找最大)
这样找的是峰值 递归式是 $T(A_{mn})=T(A_{mn/2})+\Theta(m)$
解出来就是上边的那个复杂度了