Similarity Matrix Transformation

Medium

In linear algebra, generalized similarity transformations provide a powerful mechanism for changing the coordinate basis of a matrix while preserving certain structural properties. This family of transformations is fundamental to numerous applications in machine learning, control theory, and numerical analysis. The Transformation Formula Given three square matrices A, T, and S of the same dimensions, the generalized similarity transformation computes a new matrix B using the formula: $$B = T^{-1} A S$$ Where: A is the original matrix to be transformed T is the left transformation matrix (must be invertible) S is the right transformation matrix (must be invertible) T⁻¹ denotes the inverse of matrix T B is the resulting transformed matrix Mathematical Interpretation This transformation can be understood as a change of basis operation. If we consider A as a linear operator in some original coordinate system, then: T represents how input coordinates are transformed from the new basis to the old S represents how output coordinates are transformed from the old basis to the new The result B represents the same underlying linear operation expressed in the new coordinate system Invertibility Requirement For this transformation to be mathematically valid: Matrix T must be invertible (non-singular), meaning det(T) ≠ 0 Matrix S must also be invertible for the transformation to be well-defined in applications If either T or S is singular (i.e., has a determinant of zero), the transformation cannot be computed, and the function should indicate this failure. Special Case: Classical Similarity Transformation When T = S, the formula reduces to T⁻¹AT, which is the classical similarity transformation. Matrices related by classical similarity transformations share important properties: Same eigenvalues Same determinant Same trace Same characteristic polynomial Your Task Implement a Python function that performs the generalized similarity transformation. The function should: Verify that both T and S are invertible by checking if their determinants are non-zero (or sufficiently far from zero for numerical stability) Compute and return T⁻¹AS if both matrices are invertible Return -1 if either T or S is singular (non-invertible)

Example 1

Input

A = [[1, 2], [3, 4]]
T = [[2, 0], [0, 2]]
S = [[1, 1], [0, 1]]

Output

[[0.5, 1.5], [1.5, 3.5]]

Explanation

Both T and S are invertible: • T is a scaling matrix with det(T) = 4 ≠ 0 • S is a shear matrix with det(S) = 1 ≠ 0 Step 1: Compute T⁻¹ = [[0.5, 0], [0, 0.5]] Step 2: Compute T⁻¹ × A: [[0.5, 0], [0, 0.5]] × [[1, 2], [3, 4]] = [[0.5, 1], [1.5, 2]] Step 3: Multiply by S: [[0.5, 1], [1.5, 2]] × [[1, 1], [0, 1]] = [[0.5, 1.5], [1.5, 3.5]] The final transformed matrix is [[0.5, 1.5], [1.5, 3.5]].

Example 2

Input

A = [[1, 2], [3, 4]]
T = [[1, 0], [0, 1]]
S = [[1, 0], [0, 1]]

Output

[[1.0, 2.0], [3.0, 4.0]]

Explanation

When both T and S are identity matrices: • T⁻¹ = T = I (identity matrix) • The transformation becomes: I × A × I = A The identity transformation preserves the original matrix, demonstrating that any matrix is 'similar' to itself under the identity transformation.

Example 3

Input

A = [[1, 2], [3, 4]]
T = [[1, 2], [2, 4]]
S = [[1, 0], [0, 1]]

Output

-1

Explanation

Matrix T = [[1, 2], [2, 4]] has a determinant of: det(T) = (1 × 4) - (2 × 2) = 4 - 4 = 0 Since det(T) = 0, the matrix T is **singular** (non-invertible). This means T⁻¹ does not exist, and the transformation T⁻¹AS cannot be computed. The function correctly returns -1 to indicate this invalid operation.

Constraints

1 ≤ n ≤ 50 (matrix dimensions)
All matrices A, T, and S are square matrices of the same dimension n × n
-10³ ≤ A[i][j], T[i][j], S[i][j] ≤ 10³
Matrix elements may be integers or floating-point numbers
A matrix is considered singular if |det| < 10⁻⁹ (for numerical stability)
Output values should be rounded to reasonable precision (typically float64 precision)

Preparing your editor. You can read the problem while it loads.

Similarity Matrix Transformation

Medium

In linear algebra, generalized similarity transformations provide a powerful mechanism for changing the coordinate basis of a matrix while preserving certain structural properties. This family of transformations is fundamental to numerous applications in machine learning, control theory, and numerical analysis. The Transformation Formula Given three square matrices A, T, and S of the same dimensions, the generalized similarity transformation computes a new matrix B using the formula: $$B = T^{-1} A S$$ Where: A is the original matrix to be transformed T is the left transformation matrix (must be invertible) S is the right transformation matrix (must be invertible) T⁻¹ denotes the inverse of matrix T B is the resulting transformed matrix Mathematical Interpretation This transformation can be understood as a change of basis operation. If we consider A as a linear operator in some original coordinate system, then: T represents how input coordinates are transformed from the new basis to the old S represents how output coordinates are transformed from the old basis to the new The result B represents the same underlying linear operation expressed in the new coordinate system Invertibility Requirement For this transformation to be mathematically valid: Matrix T must be invertible (non-singular), meaning det(T) ≠ 0 Matrix S must also be invertible for the transformation to be well-defined in applications If either T or S is singular (i.e., has a determinant of zero), the transformation cannot be computed, and the function should indicate this failure. Special Case: Classical Similarity Transformation When T = S, the formula reduces to T⁻¹AT, which is the classical similarity transformation. Matrices related by classical similarity transformations share important properties: Same eigenvalues Same determinant Same trace Same characteristic polynomial Your Task Implement a Python function that performs the generalized similarity transformation. The function should: Verify that both T and S are invertible by checking if their determinants are non-zero (or sufficiently far from zero for numerical stability) Compute and return T⁻¹AS if both matrices are invertible Return -1 if either T or S is singular (non-invertible)

Example 1

Input

A = [[1, 2], [3, 4]]
T = [[2, 0], [0, 2]]
S = [[1, 1], [0, 1]]

Output

[[0.5, 1.5], [1.5, 3.5]]

Explanation

Example 2

Input

A = [[1, 2], [3, 4]]
T = [[1, 0], [0, 1]]
S = [[1, 0], [0, 1]]

Output

[[1.0, 2.0], [3.0, 4.0]]

Explanation

Example 3

Input

A = [[1, 2], [3, 4]]
T = [[1, 2], [2, 4]]
S = [[1, 0], [0, 1]]

Output

-1

Explanation

Constraints

1 ≤ n ≤ 50 (matrix dimensions)
All matrices A, T, and S are square matrices of the same dimension n × n
-10³ ≤ A[i][j], T[i][j], S[i][j] ≤ 10³
Matrix elements may be integers or floating-point numbers
A matrix is considered singular if |det| < 10⁻⁹ (for numerical stability)
Output values should be rounded to reasonable precision (typically float64 precision)