linear algebra
Cramer's rule
system of linear equations


Given


 




{





a

1


x
+

b

1


y
+

c

1


z


=



d

1









a

2


x
+

b

2


y
+

c

2


z


=



d

2









a

3


x
+

b

3


y
+

c

3


z


=



d

3












{\displaystyle \left\{{\begin{matrix}a_{1}x+b_{1}y+c_{1}z&={\color {red}d_{1}}\\a_{2}x+b_{2}y+c_{2}z&={\color {red}d_{2}}\\a_{3}x+b_{3}y+c_{3}z&={\color {red}d_{3}}\end{matrix}}\right.}




which in matrix format is



 





[




a

1





b

1





c

1







a

2





b

2





c

2







a

3





b

3





c

3





]




[



x




y




z



]


=


[






d

1











d

2











d

3







]


.


{\displaystyle {\begin{bmatrix}a_{1}&b_{1}&c_{1}\\a_{2}&b_{2}&c_{2}\\a_{3}&b_{3}&c_{3}\end{bmatrix}}{\begin{bmatrix}x\\y\\z\end{bmatrix}}={\begin{bmatrix}{\color {red}d_{1}}\\{\color {red}d_{2}}\\{\color {red}d_{3}}\end{bmatrix}}.}




Then the values of 



x
,
y


{\displaystyle x,y}

 and 



z


{\displaystyle z}

 can be found as follows:







x
=



|






d

1







b

1





c

1









d

2







b

2





c

2









d

3







b

3





c

3





|


|




a

1





b

1





c

1







a

2





b

2





c

2







a

3





b

3





c

3





|



,

y
=



|




a

1







d

1







c

1







a

2







d

2







c

2







a

3







d

3







c

3





|


|




a

1





b

1





c

1







a

2





b

2





c

2







a

3





b

3





c

3





|



,

 and 

z
=



|




a

1





b

1







d

1









a

2





b

2







d

2









a

3





b

3







d

3







|


|




a

1





b

1





c

1







a

2





b

2





c

2







a

3





b

3





c

3





|



.


{\displaystyle x={\frac {\begin{vmatrix}{\color {red}d_{1}}&b_{1}&c_{1}\\{\color {red}d_{2}}&b_{2}&c_{2}\\{\color {red}d_{3}}&b_{3}&c_{3}\end{vmatrix}}{\begin{vmatrix}a_{1}&b_{1}&c_{1}\\a_{2}&b_{2}&c_{2}\\a_{3}&b_{3}&c_{3}\end{vmatrix}}},\quad y={\frac {\begin{vmatrix}a_{1}&{\color {red}d_{1}}&c_{1}\\a_{2}&{\color {red}d_{2}}&c_{2}\\a_{3}&{\color {red}d_{3}}&c_{3}\end{vmatrix}}{\begin{vmatrix}a_{1}&b_{1}&c_{1}\\a_{2}&b_{2}&c_{2}\\a_{3}&b_{3}&c_{3}\end{vmatrix}}},{\text{ and }}z={\frac {\begin{vmatrix}a_{1}&b_{1}&{\color {red}d_{1}}\\a_{2}&b_{2}&{\color {red}d_{2}}\\a_{3}&b_{3}&{\color {red}d_{3}}\end{vmatrix}}{\begin{vmatrix}a_{1}&b_{1}&c_{1}\\a_{2}&b_{2}&c_{2}\\a_{3}&b_{3}&c_{3}\end{vmatrix}}}.}






Task
Given the following system of equations:









{



2
w
−
x
+
5
y
+
z
=
−
3




3
w
+
2
x
+
2
y
−
6
z
=
−
32




w
+
3
x
+
3
y
−
z
=
−
47




5
w
−
2
x
−
3
y
+
3
z
=
49








{\displaystyle {\begin{cases}2w-x+5y+z=-3\\3w+2x+2y-6z=-32\\w+3x+3y-z=-47\\5w-2x-3y+3z=49\\\end{cases}}}




solve for 



w


{\displaystyle w}

, 



x


{\displaystyle x}

, 



y


{\displaystyle y}

 and 



z


{\displaystyle z}

, using Cramer's rule.




#include <algorithm>
#include <iostream>
#include <vector>
 
class SubMatrix {
    const std::vector<std::vector<double>> *source;
    std::vector<double> replaceColumn;
    const SubMatrix *prev;
    size_t sz;
    int colIndex = -1;
 
public:
    SubMatrix(const std::vector<std::vector<double>> &src, const std::vector<double> &rc) : source(&src), replaceColumn(rc), prev(nullptr), colIndex(-1) {
        sz = replaceColumn.size();
    }
 
    SubMatrix(const SubMatrix &p) : source(nullptr), prev(&p), colIndex(-1) {
        sz = p.size() - 1;
    }
 
    SubMatrix(const SubMatrix &p, int deletedColumnIndex) : source(nullptr), prev(&p), colIndex(deletedColumnIndex) {
        sz = p.size() - 1;
    }
 
    int columnIndex() const {
        return colIndex;
    }
    void columnIndex(int index) {
        colIndex = index;
    }
 
    size_t size() const {
        return sz;
    }
 
    double index(int row, int col) const {
        if (source != nullptr) {
            if (col == colIndex) {
                return replaceColumn[row];
            } else {
                return (*source)[row][col];
            }
        } else {
            if (col < colIndex) {
                return prev->index(row + 1, col);
            } else {
                return prev->index(row + 1, col + 1);
            }
        }
    }
 
    double det() const {
        if (sz == 1) {
            return index(0, 0);
        }
        if (sz == 2) {
            return index(0, 0) * index(1, 1) - index(0, 1) * index(1, 0);
        }
        SubMatrix m(*this);
        double det = 0.0;
        int sign = 1;
        for (size_t c = 0; c < sz; ++c) {
            m.columnIndex(c);
            double d = m.det();
            det += index(0, c) * d * sign;
            sign = -sign;
        }
        return det;
    }
};
 
std::vector<double> solve(SubMatrix &matrix) {
    double det = matrix.det();
    if (det == 0.0) {
        throw std::runtime_error("The determinant is zero.");
    }
 
    std::vector<double> answer(matrix.size());
    for (int i = 0; i < matrix.size(); ++i) {
        matrix.columnIndex(i);
        answer[i] = matrix.det() / det;
    }
    return answer;
}
 
std::vector<double> solveCramer(const std::vector<std::vector<double>> &equations) {
    int size = equations.size();
    if (std::any_of(
        equations.cbegin(), equations.cend(),
        [size](const std::vector<double> &a) { return a.size() != size + 1; }
    )) {
        throw std::runtime_error("Each equation must have the expected size.");
    }
 
    std::vector<std::vector<double>> matrix(size);
    std::vector<double> column(size);
    for (int r = 0; r < size; ++r) {
        column[r] = equations[r][size];
        matrix[r].resize(size);
        for (int c = 0; c < size; ++c) {
            matrix[r][c] = equations[r][c];
        }
    }
 
    SubMatrix sm(matrix, column);
    return solve(sm);
}
 
template<typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
    auto it = v.cbegin();
    auto end = v.cend();
 
    os << '[';
    if (it != end) {
        os << *it++;
    }
    while (it != end) {
        os << ", " << *it++;
    }
 
    return os << ']';
}
 
int main() {
    std::vector<std::vector<double>> equations = {
        { 2, -1,  5,  1,  -3},
        { 3,  2,  2, -6, -32},
        { 1,  3,  3, -1, -47},
        { 5, -2, -3,  3,  49},
    };
 
    auto solution = solveCramer(equations);
    std::cout << solution << '\n';
 
    return 0;
}