Two-Dimensional Orthonormal Basis Generator

Medium

In linear algebra, an orthonormal basis is a set of vectors that are both mutually orthogonal (perpendicular to each other) and normalized (each has unit length). Constructing such a basis is fundamental for simplifying computations in vector spaces, as it allows any vector to be uniquely expressed as a linear combination of basis vectors using simple dot products. The Gram-Schmidt Orthogonalization Process is a classical algorithm that transforms a set of linearly independent vectors into an orthonormal set spanning the same subspace. The algorithm works iteratively: Normalize the first vector to obtain the first basis vector For each subsequent vector: Subtract projections onto all previously computed basis vectors (removing components parallel to existing basis vectors) Check if the resulting vector has sufficient magnitude (greater than the tolerance threshold) If yes, normalize the result to add a new orthonormal basis vector If no, the vector was linearly dependent and is discarded Mathematical Formulation: Given input vectors v₁, v₂, ..., vₖ, the orthonormal basis vectors u₁, u₂, ..., uₙ are computed as: $$u_1 = \frac{v_1}{|v_1|}$$ For each subsequent vector vᵢ: $$w_i = v_i - \sum_{j=1}^{i-1} \text{proj}_{u_j}(v_i)$$ where the projection is: $\text{proj}_u(v) = (v \cdot u) \cdot u$ If $|w_i| > \text{tol}$, then: $u_i = \frac{w_i}{|w_i|}$ Your Task: Write a Python function that computes an orthonormal basis for the subspace spanned by a list of 2D vectors using the Gram-Schmidt process. The function should: Accept a list of 2D vectors and a tolerance value for determining linear independence Return a list of orthonormal vectors (unit length and mutually perpendicular) spanning the same subspace Discard any vector that becomes nearly zero after projection removal (norm ≤ tolerance)

Example 1

Input

vectors = [[1.0, 0.0], [1.0, 1.0]]
tol = 1e-10

Output

[[1.0, 0.0], [0.0, 1.0]]

Explanation

**Step 1:** Take the first vector [1.0, 0.0]. Its norm is 1.0, so normalizing it gives u₁ = [1.0, 0.0]. **Step 2:** Take the second vector [1.0, 1.0]. Compute its projection onto u₁: • proj_u₁(v₂) = ([1.0, 1.0] · [1.0, 0.0]) × [1.0, 0.0] = 1.0 × [1.0, 0.0] = [1.0, 0.0] Subtract the projection: • w₂ = [1.0, 1.0] - [1.0, 0.0] = [0.0, 1.0] The norm of w₂ is 1.0, which is greater than the tolerance 1e-10. Normalize to get u₂ = [0.0, 1.0]. **Result:** The orthonormal basis is [[1.0, 0.0], [0.0, 1.0]], which are the standard unit vectors.

Example 2

Input

vectors = [[3.0, 0.0], [0.0, 4.0]]
tol = 1e-10

Output

[[1.0, 0.0], [0.0, 1.0]]

Explanation

**Step 1:** Take [3.0, 0.0]. Its norm is 3.0. Normalize: u₁ = [3.0/3.0, 0.0/3.0] = [1.0, 0.0]. **Step 2:** Take [0.0, 4.0]. Compute projection onto u₁: • proj_u₁(v₂) = ([0.0, 4.0] · [1.0, 0.0]) × [1.0, 0.0] = 0 × [1.0, 0.0] = [0.0, 0.0] Subtract projection: • w₂ = [0.0, 4.0] - [0.0, 0.0] = [0.0, 4.0] Norm of w₂ is 4.0 > 1e-10. Normalize: u₂ = [0.0, 1.0]. **Observation:** The input vectors were already orthogonal (perpendicular to each other), so the algorithm only needed to normalize them.

Example 3

Input

vectors = [[1.0, 0.0], [0.0, 1.0]]
tol = 1e-10

Output

[[1.0, 0.0], [0.0, 1.0]]

Explanation

**Input Analysis:** The input vectors [1.0, 0.0] and [0.0, 1.0] are already orthonormal: • They have unit length: ||[1.0, 0.0]|| = 1.0, ||[0.0, 1.0]|| = 1.0 • They are orthogonal: [1.0, 0.0] · [0.0, 1.0] = 0 **Algorithm Verification:** • u₁ = [1.0, 0.0] (already normalized) • For [0.0, 1.0]: projection onto u₁ is zero, so w₂ = [0.0, 1.0] • ||w₂|| = 1.0 > tol, normalize to get u₂ = [0.0, 1.0] **Result:** The output equals the input since the vectors were already orthonormal.

Constraints

Each vector in the input list is a 2D vector with exactly 2 floating-point components
1 ≤ number of input vectors ≤ 100
-10⁶ ≤ vector components ≤ 10⁶
The tolerance value tol satisfies 10⁻¹⁵ ≤ tol ≤ 10⁻¹
At least one input vector must be non-zero (have norm > tolerance)
Input vectors may be linearly dependent; the algorithm should handle this gracefully

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

Two-Dimensional Orthonormal Basis Generator

Medium

In linear algebra, an orthonormal basis is a set of vectors that are both mutually orthogonal (perpendicular to each other) and normalized (each has unit length). Constructing such a basis is fundamental for simplifying computations in vector spaces, as it allows any vector to be uniquely expressed as a linear combination of basis vectors using simple dot products. The Gram-Schmidt Orthogonalization Process is a classical algorithm that transforms a set of linearly independent vectors into an orthonormal set spanning the same subspace. The algorithm works iteratively: Normalize the first vector to obtain the first basis vector For each subsequent vector: Subtract projections onto all previously computed basis vectors (removing components parallel to existing basis vectors) Check if the resulting vector has sufficient magnitude (greater than the tolerance threshold) If yes, normalize the result to add a new orthonormal basis vector If no, the vector was linearly dependent and is discarded Mathematical Formulation: Given input vectors v₁, v₂, ..., vₖ, the orthonormal basis vectors u₁, u₂, ..., uₙ are computed as: $$u_1 = \frac{v_1}{|v_1|}$$ For each subsequent vector vᵢ: $$w_i = v_i - \sum_{j=1}^{i-1} \text{proj}_{u_j}(v_i)$$ where the projection is: $\text{proj}_u(v) = (v \cdot u) \cdot u$ If $|w_i| > \text{tol}$, then: $u_i = \frac{w_i}{|w_i|}$ Your Task: Write a Python function that computes an orthonormal basis for the subspace spanned by a list of 2D vectors using the Gram-Schmidt process. The function should: Accept a list of 2D vectors and a tolerance value for determining linear independence Return a list of orthonormal vectors (unit length and mutually perpendicular) spanning the same subspace Discard any vector that becomes nearly zero after projection removal (norm ≤ tolerance)

Example 1

Input

vectors = [[1.0, 0.0], [1.0, 1.0]]
tol = 1e-10

Output

[[1.0, 0.0], [0.0, 1.0]]

Explanation

Example 2

Input

vectors = [[3.0, 0.0], [0.0, 4.0]]
tol = 1e-10

Output

[[1.0, 0.0], [0.0, 1.0]]

Explanation

Example 3

Input

vectors = [[1.0, 0.0], [0.0, 1.0]]
tol = 1e-10

Output

[[1.0, 0.0], [0.0, 1.0]]

Explanation

Constraints

Each vector in the input list is a 2D vector with exactly 2 floating-point components
1 ≤ number of input vectors ≤ 100
-10⁶ ≤ vector components ≤ 10⁶
The tolerance value tol satisfies 10⁻¹⁵ ≤ tol ≤ 10⁻¹
At least one input vector must be non-zero (have norm > tolerance)
Input vectors may be linearly dependent; the algorithm should handle this gracefully