Question

In the mysterious Grand Library of Alexandria (which secretly still exists!), historians discovered an ancient library containing some sacred knowledge in the form of books. The books were so holy that each one was kept in a vault and each unique vault was locked by a unique pattern, an n-dimensional vector.

Young apprentice librarian Maya found a set of keys lying on the floor along with a scroll. The scroll contained a spell that could work on a set of keys and generate all possible keys to open all possible vaults of the library. The spell combines the keys in a linear way.

Help Maya find if the set of keys she found is sufficient enough and also fewest possible to generate all possible keys and unlock all the vaults of the library. Help Maya write a program that checks this.

Note: Since the ancient mechanism works with real numbers, your solution should handle floating-point arithmetic carefully.

from typing import List

def can_unlock_library(keys: List[List[float]], tolerance: float = 1e-10) -> bool:
    """
    Args:
        keys: List of n vectors, each being a list of n floating-point numbers
        precision: Threshold for numerical calculations (default: 1e-10)

    Returns:
        bool: True if keys can unlock the library, False otherwise
    """
    pass

Example:

keys = [
    [1.0, 0.0, 0.0],
    [0.0, 1.0, 0.0],
    [0.0, 0.0, 1.0]
]
result = can_unlock_library(keys)  # Returns True

Explanation:

The set of provided keys are fewest possible keys that can generate all possible keys in 3-dimensional space when combined linearly and hence can unlock all the vaults of the library.

keys = [
    [2, 0, 0],
    [0, 2, 0],
    [4, 4, 0]
]
result = can_unlock_library(keys)  # Returns False

Explanation:

The set of provided keys cannot represent the key [0, 0, 1]. Hence all possible keys required to unlock the library.

Solution

Here’s the code for reference and some notes on the solution below.

Each key is an n-dim vector. The set of keys should be

1. fewest possible
2. able to generate all possible keys in n-dim space

This means we need to check if the provied set of vectors form a basis.

What is a Basis?

1. A basis is a set of vectors that are linearly independent and spans the space.
2. For an n-dimensional space, a basis must have exactly n vectors
3. These vectors must not be able to be expressed as linear combinations of each other hence linearly independent

What is linear independence?

A set of vectors are linearly independent when none of these vectors can be expressed as a linear combination of the others. Following set of vectors are linearly independent

v1 = (1, 0, 0)
v2 = (0, 1, 0)
v3 = (0, 0, 1)

and

v1 = (1, 1, 0)
v2 = (1, 0, 1)
v3 = (0, 1, 1)

and even

v1 = (3, -4, 7)
v2 = (-2, 5, 1)
v3 = (6, 2, -3)

none of these vectors can be expressed as a linear combination of the others. But the following are not independent as one is double the other.

v1 = (1,1)
v2 = (2,2)

Test for linear independence

We can use QR decomposition to test for linear independence.

Test for spanning the space

1. Vectors should be linearly independent
2. nuumber of vectors = number of dimensions

Here’s an example of three vectors that span the 3-dimensional space

v₁ = (1, 0, 2)
v₂ = (0, 1, -1)
v₃ = (2, 1, 0)

You can reach any point (x, y, z) in 3-dim space using some combination of these vectors. i.e. c1(1,0,2) + c2(0,1,-1) + c3(2,1,0) = (a,b,c)

This system will always have a solution for any (a,b,c), proving these vectors span the space. Another simple example is

e₁ = (1, 0, 0)
e₂ = (0, 1, 0)
e₃ = (0, 0, 1)

Why this matters?

1. Basis vectors are used in Principal Component Analysis (PCA) to reduce feature dimensions while preserving maximum variance.
2. It improves model performance by picking minimal independent features
3. Basis vectors help identify optimal subspaces for weight initialization and regularization in Neural Networks.
4. Techniques like Singular Value Decomposition (SVD) use basis vectors to decompose matrices for recommendation systems.
5. Basis vectors in vector space models represent and compare documents in natural language processing.