Skip to content

Instantly share code, notes, and snippets.

@ORESoftware
Last active October 20, 2022 15:34
Show Gist options
  • Save ORESoftware/2a4bf2d131e75f986defc9f624f13809 to your computer and use it in GitHub Desktop.
Save ORESoftware/2a4bf2d131e75f986defc9f624f13809 to your computer and use it in GitHub Desktop.
algorithm - quickly determine if two numeric JS arrays are linearly independent

This is an algorithm (function) that accepts two numeric JS/TS arrays and returns a boolean value representing whether the two arrays are linearly independent. This would be for a linear library or linear optimization - in my case - checking constraints for redundancy or contradictions.

Assumptions:

1. Same size arrays
2. If size is less than 2, undefined results
3. None of the arrays are the zero-vector [0,0,0,0,0,...,0]
4. For any given pair, if the numerator or denominator is zero and the other non-zero, 
then we know they arrays are independent and can return early.

Algorithm in English:

(We return early if the arrays are independent).

  • We store the ratio of the first entries, a[0]/b[0].
  • If any subsequent pair of values a[1]/b[1] or a[2]/b[2] has a different ratio, then the arrays are independent and we return early.
  • If first pair is both zero, we don't know anything and have to continue to next pair.



As an example: If we find ourselves at the 15th element, then we know that either:

(a) that the ratio between pairs 0-14 are all equal.
(b) or that all pairs are a[i]/b[i] are 0/0 (which is roughly equivalent to (a)).


Ergo, there is no reason to store anything other than the ratio of the first pair a[0]/b[0].

import * as math from 'mathjs';


const areIndependent = (a: Array<number>, b: Array<number>): Boolean => {

    if (a.length !== b.length) {
        throw new Error('hard to believe these arrays are not the same length but they not')
    }

    if (a[0] !== 0 && b[0] === 0) {
        return true;
    }

    if (a[0] === 0 && b[0] !== 0) {
        return true;
    }

    const firstFactor = b[0] === 0 ? 'Div/by/0' : math.divide(a[0], b[0]);  

    for (let j = 1; j < a.length; j++) {

        if (a[j] === 0 && b[j] !== 0) {
            return true;
        }

        if (a[j] !== 0 && b[j] === 0) {
            return true;
        }

        if(b[j] === 0){
            // both are 0, nothing new here
            if(firstFactor !== 'Div/by/0'){
                return true;
            }
            continue;
        }

        if(firstFactor === 'Div/by/0'){
            return true;
        }

        const currFactor = math.divide(a[j], b[j]);
        if (!math.equal(currFactor, firstFactor)) {
            return true;
        }
    }
    return false;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment