# How to solve a large system of linear algebra?

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.

• Welcome to Mathematics Stack Exchange! A quick tour will enhance your experience. Here are helpful tips to write a good question and write a good answer. For equations, please use MathJax. – dantopa Feb 28 at 23:27
• With a computer you could run Gaussian elimination, though it's not obvious to me that the solution over vectors of 26 real numbers is actually unique (because if any solution exists, then at least 18 of the equations are redundant, so what's to stop more than 18 of them from being redundant?) – Ian Mar 1 at 0:07
• Didn't noticed Albuquerque was so close to Jamestown. – zwim Mar 1 at 0:21

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.

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.

• you can also $Q=13\times27-(a+b+\cdots+z)$ – zwim Mar 1 at 8:04

# 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$$.

• Your data contains a typo: "SAN ANTONILO" instead of "SAN ANTONIO". Perhaps that will work better? – FredH Mar 1 at 0:51
• The problem says the values are distinct whole numbers from $1$ to $26$, so $Q = 1$ and ALBUQUERQUE $= 102$. – FredH Mar 1 at 1:07