How to solve a large system of linear algebra?

Question

A friend has given me the following puzzle to solve, however, I lack the linear algebra knowledge to calculate the solution, and my attempts to brute force the solution have been foiled by a large number of combinations.

The Problem:

Every letter in the alphabet is assigned a whole number from $1-26$. No two letters have the same number. Below is a list of $44$ words and the value of their letters added up. For example, if $O=11$, $H=23$, $I=2$, OHIO would equal $11+23+2+11 = 47$ (these values are not necessarily correct).

find the value of ALBUQUERQUE (added in the same manner). Thanks for any solutions or ideas.

Answer 1

To solve it by hand you need to look for words that have similar sets of letters. Using OREGON and RENO you know $G+O=28$. It's too bad they didn't give you ARKANSAS. RENO and NOME give $M=R+3$. Can you find $D+A-O=17?$ MONTGOMERY and MONTEREY are interesting. It is supposed to be a certain amount of work.

Answer 2

Linear System

Craft a linear system. ALASKA represents $3\times A + L + K + S = 73$ ...

Definitions:

$n=44$, number of names

$m=26$, number of letters in alphabet

Linear System

Create the linear system $\mathbf{A}x = b$ where $\mathbf{A}\in\mathbb{R}^{44\times 26}$

System matrix

Rules for building $\mathbf{A}$:

Each row corresponds to a name. E.g. ALASKA is in row $1$, WICHITA in row $44$.

Each column corresponds to a letter. E.g. A is $1$, Z is $26$.

Example: ALASKA has 3 A, 1 K, 1 L, 1 S. The non-zero entries of the first row are: $$\mathbf{A}_{1,1} = 3, \quad \mathbf{A}_{1,11} = 1, \quad \mathbf{A}_{1,12} = 1, \quad \mathbf{A}_{1,19} = 1$$

Array plots

The system matrix and data vector are plotted below.

Solution via Gaussian Elimination

Thanks to astute reader @FredH, the system can be solved exactly by elementary means.

\begin{array}{cc} \text{A} & 10 \\ \text{B} & 20 \\ \text{C} & 3 \\ \text{D} & 12 \\ \text{E} & 6 \\ \text{F} & 15 \\ \text{G} & 23 \\ \text{H} & 13 \\ \text{I} & 24 \\ \text{J} & 9 \\ \text{K} & 16 \\ \text{L} & 19 \\ \text{M} & 21 \\ \text{N} & 4 \\ \text{O} & 5 \\ \text{P} & 22 \\ \text{Q} & 0 \\ \text{R} & 18 \\ \text{S} & 8 \\ \text{T} & 14 \\ \text{U} & 7 \\ \text{V} & 26 \\ \text{W} & 25 \\ \text{X} & 11 \\ \text{Y} & 17 \\ \text{Z} & 2 \\ \end{array}

Raw data

To spare others from tedious typing, here is the data in cut and paste form.

b = (73,56,134,64,73,64,78,88,81,64,129,85,56,102,68,77,91,56,105,77,81,83,91,49,109,111,36,61,72,157,47,58,93,65,61,44,70,122,33,69,106,91,99,113)

(ALASKA, HOUSTON, MONTGOMERY, SALEM, ARIZONA, IDAHO, NANTUCKET, SAN ANTONILO, ATLANTA, IOWA, NASHVILLE, SAVANNAH, BOSTON, JAMESTOWN, NEVADA, SEATTLE, BUFFALO, KANSAS, NEW ORLEANS, TAMPA, CHICAGO, KENTUCKY, NEW YORK, TEXAS, COLUMBIA, LOUISIANA, NOME, TOLEDO, DENVER, LOUISVILLE, OHIO, TULSA, DETROIT, MAINE, OREGON, UTAH, EL PASO, MICHIGAN, RENO, VENICE, HAWAII, MONTEREY, SACRAMENTO, WICHITA)

Albuquerque

As pointed out by @FredH (again), the value of $Q=1$ by the process of elimination.

The row vector for ALBUQUERQUE is $$\{1,1,0,0,2,0,0,0,0,0,0,1,0,0,0,0,2,1,0,0,3,0,0,0,0,0\}.$$ The dot product of this vector with the solution vector $=100$.

Final answer: ALBUQUERQUE $= 100 + 2Q = 102$.

Answer 3

This question has already been answered sufficiently by dantopa with the addition of the comment by FredH. However, I'll just put some Java/MATLAB code here for the sake of completeness, and so you can see how to solve a problem like this using a computer.

Java:

import java.util.*;

public static void main(String args[]) {

String[] names = {"alaska", "arizona", "atlanta", "boston", "buffalo", "chicago", "columbia", "denver", "detroit", "elpaso", "hawaii", "houston", "idaho", "iowa", 
        "jamestown", "kansas", "kentucky", "louisiana", "louisville", "maine", "michigan", "monterey", "montgomery", "nantucket", "nashville", "nevada", "neworleans", "newyork", "nome",
        "ohio", "oregon", "reno", "sacramento", "salem", "sanantonio", "savannah", "seattle", "tampa", "texas", "toledo", "tulsa", 
        "utah", "venice", "wichita"};



int[][] x = new int[44][26];


int count = 0;
int value = 0;

for(String y :names) {
    for(int i = 0; i < y.length(); i++) {
        value = (int)y.charAt(i) - 97; // I looked up an ASCII table because chars are stored as integers and subtracted 97 to that a would be at the first index.
        x[count][value]++;
    }
    count++;
}

System.out.print("["); // This is just printing out in a convenient form so I we can copy it into MATLAB easily
for(int i = 0; i < 44; i++) {
    for(int j = 0; j < 26; j++) {
        System.out.print(x[i][j]);
        if(j < 25) System.out.print(",");
    }
    System.out.println(";");
}

System.out.println("]");
}}

Ok copy the output MATLAB (you could do it in some Java library or done this first part in MATLAB however I don't like doing normal programming on MATLAB or doing math in Java)

In MATLAB:

a = \\paste the output from java here: b = [73, 73, 81, 56, 91, 81, 109, 72, 93, 70, 106, 56, 64, 64, 102, 56, 83, 111, 157, 65, 122, 91, 134, 78, 129, 68, 105, 91, 36, 47, 61, 33, 99, 64, 88, 85, 77, 77, 49, 61, 58, 44, 69, 113]; b = b'; x = a\b

The output will be all the solutions in alphabetical order, however $Q$ will be $0$. Since the problem called for numbers between $1$ and $26$, just replace it with the number which is not included already. It is $1$, so you can deduce that $Q = 1$ and use it to calculate the value of Albuquerque.