Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [gaussian-elimination]

For questions on or related to the technique of Gaussian elimination, used in solving systems of linear equations.

0
votes
0answers
34 views

Why do solving a $4\times4$ matrix using Gaussian elimination have $58.66$ arithmetic operations?

The question reads "Show that the total number of arithmetic (multiplication, divisions and additions) operations needed to solve the matrix below using Gaussian elimination is approximately 58.66". ...
0
votes
1answer
39 views

Factoring $9788111$ via Gaussian elimination over $\mathbb F_2$

I am trying to follow page 142 to page 144 of An Introduction to Mathematical Cryptography by Hoffstein, Pipher & Silverman, where they give an example using Gaussian elimination over $\mathbb F_2$...
1
vote
1answer
52 views

Let $I$ be a LES with its solution set $\mathcal{L}_I$ and some other solution $\mathcal{L}_2$. Is $\mathcal{L}_2\subseteq \mathcal{L}_{I}$ or not?

We have the following LES $I$ \begin{align} 3x_1-2x_2+4x_3-x_4&=1\\ -\frac43x_2-\frac{13}3x_3+\frac13x_4&=-\frac{19}3 \end{align} with the solution set $\mathcal{L}_{I}$, which contains ...
0
votes
0answers
12 views

determine general solution for this linear system

lateX of linear system to view more clearly I have find a general solution to this linear system (included a link to lateX pic): x_1 - 2x_2 + x_3 - 3x_4 = 1 2x_1 - 4x_2 + 4x_3 + 6x_4 + 4x_5 = 6 -...
0
votes
0answers
19 views

Using LU Decomposition to find determinants

I've been trying to find advantages and disadvantages to using LU factorisation with pivoting to compute determinants. There's a lot of information on its usefulness in regards to solving systems of ...
1
vote
0answers
23 views

Gaussian elimination in vector spaces

I've been working on a set of problems while learning matrix operations as well as vector spaces and subspaces. But now I have some doubts that go outside the general rule of thumb and I'm unable to ...
0
votes
0answers
22 views

Determining all possible ways to perform gaussian elimination on a linear system of equations

My first question is quite general: consider a linear system \begin{equation} A\vec{x}=\vec{b}, \end{equation} with $A\in\{-1,0,1\}^{n^2}$ being a full rank matrix and $\vec{x},\vec{b}\in\mathbb{R}^n$...
0
votes
0answers
14 views

Elimination Matrix Specific entry question

Given a $3 \times 3$ array $$ A =\begin{bmatrix} 1 & 2 &1 \\ 3 & 8 & 1 \\ 0 &4 &1 \end{bmatrix}, $$ My understanding is that that I subtract $3$ times row one from row two to ...
0
votes
1answer
35 views

Solving a linear equation system with 3 equations and 5 unknowns

I'm trying to solve this system with 3 equations and 5 unknowns: $$\left\{\matrix{x_1+x_2-2x_3+x_4+3x_5=1\\2x_1-x_2+2x_3+2x_4+6x_5=2\\3x_1+2x_2-4x_3-3x_4-9x_5=3}\right.$$ using Gaussian elimination, ...
1
vote
1answer
46 views

How to perform Gaussian elimination to invert a matrix if the matrix contains zeros on the diagonal?

I'm coding the method that inverts a matrix through Gaussian elimination. I've coded everything assuming that there are no zeros on the diagonal. For the situation where a diagonal element is zero, ...
0
votes
1answer
17 views

For what value of k is the system of equations consistent?

For $$x − y + 2z = −2$$ $$2x + 3y + 4z = 7$$ $$4x − 7y + 5z = k$$ $$8x − 4y + 6z = 2$$ Using Gaussian Elimination, I first get the below by applying $R2 - 2R1$, $R3 - 4R1$, $R4 - 8R1$ \begin{...
0
votes
1answer
28 views

For what value of $k$ does system of Equations have infinitely many solutions? Gaussian Elimination - is my approach correct?

$$ x + ky + z = 1$$ $$ - y + z = 2$$ $$x + y + 2z = 3$$ Using Gaussian elimination I reduced the augmented matrix to: [\begin{bmatrix} 1&1&2&3\\ 0&-1&1&2\\ 0&0&k-2&...
1
vote
1answer
32 views

Eigenvalue by Gaussian elimination?

Let $A=\begin{bmatrix}-1&4&0\\-2&4&-1\\2&-5&0 \end{bmatrix}$ I want to find out the eigenvalue of matrix my Gaussian elimination. My idea was to make the matrix triangular ...
0
votes
0answers
27 views

Positive Definiteness of sub-matrices when performing Gaussian elimination. [duplicate]

Let $A$ be a symmetric positive definite matrix. Is there a simple way to show, perhaps using a well known result, that the submatricies obtained by applying Gaussian elimination, $A^{(k)}= (a^{(k)}_{...
0
votes
1answer
47 views

Write the 3x3-Matrix A as product of elementary matrices ( rank(A)<3 )

Notation: https://en.wikipedia.org/wiki/Elementary_matrix#Elementary_row_operations $ a\in \mathbb{F}_{5}\\ A\in\mathbb{F}_{5}^{3x3}\\ A=\begin{pmatrix} a & a+1 & a+2 \\ a+1 & a+2 & ...
0
votes
1answer
39 views

Equation system with multiple unknown real numbers

Have been having problems with this equation system for a while, \begin{array}{l} x - y - az = 1\\ ax + y + az = a\\ ax + 3y + 3z = -1 \end{array} where I need to find all the values of $a\in \mathbb{...
1
vote
2answers
38 views

Linear system of equations that arises from recurrence relation.

So when solving a third order homogenous recurrence relation I end upp with the task of determening the constants $a,b$ and $c$. The initial conditions give rise to the following system of equations: ...
0
votes
1answer
15 views

System of equations. Find values for A.

Find the values of the parameter a for which the system has (1) one solution, (2) no solutions, and (3) infinitely many solutions. In case (3), find the solution. I'm so sorry about the picture, but ...
0
votes
1answer
13 views

Solving equation where the independent terms' vector is defined in function of the variable vector.

I'm trying to teach myself linear algebra for and one of the exercises of the book I'm reading is the following: Find all solutions in $\vec x= \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} ∈\...
0
votes
0answers
36 views

LU decomposition of matrix using column pivoting

I want to find the LU decomposition of the following matrix $A$ using Gauss algorithm and column pivoting. $$A=\begin{pmatrix}6 & 4 & 3 & 1\\ 1 & 1 & 0 & 2 \\ 2 & 3 & 1 ...
1
vote
1answer
30 views

Elementary Matrix Multiplication and Gauss Elimination

I have the following matrix: $$ A = \begin{bmatrix} 2 & 1 & 1 & 0 \\ 4 & 3 & 2 & 1 \\ 8 & 7 & 8 & 5 \\ 6 & 7 & 9 & 8 \\ \...
0
votes
0answers
21 views

Backwards substitution solutions

I am not to sure if this is more of a programming question or a question more apt for mathematics. But why is backwards substituion the preferable method for solving larger matrices on a computer?
0
votes
2answers
61 views

LU decomposition implies Gaussian Elimination without pivoting

If Gaussian elimination can be carried out without pivoting for A, then A has an LU decomposition. Is the converse true: if A has an LU decomposition, then Gaussian elimination can be carried out (in ...
0
votes
0answers
32 views

Solve the matrix equation AX = B, where X and B are matrices of size n × m

How can I solve using gauss elimination the the matrix equation AX = B, where X and B are matrices of size n × m, where the A matrix is non-singular. Using an efficient approach.
1
vote
2answers
71 views

Solve $A^k x = b$ where $k$ is a positive integer

I have to solve this system $$ A^k x = b $$ using gaussian elimination with complete pivoting in matlab. How can I implement that in an efficient way?
1
vote
0answers
59 views

Counting the number of operations in solving $Ax = b$ for a 2x2 matrix $A$

I have been tasked with showing that the number of operations needed to solve $Ax = b$ for a tridiagonal n x n matrix $A$ is $8(n-1)+1$. I tried to solve this and I was getting too large an answer, so ...
2
votes
1answer
56 views

Which one is most cost expensive to solve a linear equation? LU or inverse?

Which one is the most expensive way to solve for linear equation? LU-decomposition $$A = LU$$ Or finding the inverse $$A^{-1} = \frac{1}{\det(A)} \operatorname{adj}(A)$$ If I have to choose, I ...
0
votes
0answers
17 views

normalizing by using gaussian distribution for negative and positive numbers and feed in Min,Max normalization

I'm dealing in Python with a dataset which has 6 million float numbers belongs to 3 main parameters A, B , C and I map them in 24x20 matrices for each cycle and I plot them 480-values by 480-values. ...
0
votes
0answers
23 views

On positive definiteness of a sub-matrix after first step Gaussian elimination to a symmetric positive definite matrix

Let $A=[a_{ij}]\in M_n(\mathbb R)$ be a symmetric positive definite matrix (i.e. all eigenvalues of $A$ are real and positive ) with $a_{11}\ne 0$ . Now let $A_1=[a' _{jk}] \in M_{n-1}(\mathbb R)$ ...
0
votes
1answer
22 views

Comparing the ranks of leading princial minors of a square symmetric matrix

Let $A$ be a $n$ x $n$ real symmetric matrix and let $A_k$ denotes the $k$-th order leading principal minor matrix of $A$. Prove that for $0 \leq k \leq n-1$: $$Rank(A_{k+1})\leq Rank(A_k)+2$$ ...
1
vote
1answer
32 views

Finding number of solutions in system of three equations with four variables and one parameter

As a continuation (my previous question regarding this topic) of reminding myself Algebra I would like you to check my calculations, and if it possible - to suggest better $U$ matrix transformations. ...
0
votes
0answers
31 views

Gauss Jordan complex matrix inversion - Choice of pivot element

When inverting a matrix of consisting of complex numbers, how is the pivot element chosen? In a real matrix the smallest number is chosen, how can the choice be made when the elements are complex? ...
0
votes
2answers
37 views

Solve the following system of equations using Gaussian Elimination Method

Solve the following system of equations using Gaussian Elimination Method $$x+2y+3z=2$$ $$x+y-z=1$$ $$2x+3y+2z=3$$. My Attempt : $$x+2y+3z=2………(1)$$ $$x+y-z=1…………(2)$$ $$2x+3y+2z=3………(3)$$ ...
1
vote
1answer
45 views

How to compute amount of floating point operations for LU-decomposition of banded matrix?

I want to compute the amount of floating point operations, flops, needed for the LU-decomposition/factorization of a banded matrix A consisting of 5 nonzero diagonals. Matrix $A\in\mathbb{R}^{n \...
1
vote
1answer
156 views

Outer product reformulation of LU decomposition

For my numerical analysis class, I wanted to implement the rather simple, in-place LU decomposition algorithm. I did this the naive way and found my code was very, very slow, because I was doing every ...
0
votes
1answer
31 views

Finding values of x for linear dependence

Find all real numbers $x$ for which the matrices are linearly dependent $$M_1=\begin{bmatrix} 1&1\\x&0 \end{bmatrix}\quad M_2= \begin{bmatrix} 1&-x\\x-1&3 \end{bmatrix}$$ $$M_3= \...
0
votes
1answer
55 views

Optimal pivoting strategy in LU factorization

I'm currently reading the book Numerical Linear Algebra by Lloyd N. Trefethen and David Bau, III, working my way through the required lectures for my Numerical Analysis class. The current subject is ...
0
votes
0answers
31 views

Gaussian Elimination - Linear Algebra

I wanted to find no. of operations required to perform Gauss elimination and turns out to be $O(n^3)$. The procedure is like let's say you have $100 \times 100$ matrix then at first level we require $...
3
votes
0answers
48 views

Show that the values of the following determinants are not zero without actually finding the exact values

$$\begin{bmatrix} 111 & 100 & 225 & 235\\ 220 & 312 & 220 & 410\\ 215 & 180 & 268 & 305\\ 315 & 145 & 205 & 122 \end{bmatrix}$$ Guys is it enough to ...
0
votes
2answers
20 views

How to build a matrix out of one equation so that it can be solved with Gaussian elimination?

Find such $ a, b, c, d ∈ ℝ $ that $a(x^3 − x^2 + x − 1) + b(x^3 + x^2 + 3x−2) + c(x^2 + 3x + 1) +d(x^3 + 2x^2 − 2) + 7 = 0$ $∀x ∈ ℝ$ using Gauss' elimination. How to get from the one equation to ...
0
votes
2answers
166 views

LU decomposition of SPD matrix without partial pivoting?

I get why diagonal dominant matrices do not need partial pivoting before Gaussian elimination can be applied in order to gain a LU decomposition, but why is this also the case for SPD matrices in ...
0
votes
2answers
38 views

Find image of matrix $A$

Let $A=\begin{pmatrix}7&5&1\\-8&-6&0\\-3&-2&-1\end{pmatrix}$ find Im(A). My attempt: We know that $Im(A)=\{B=\begin{pmatrix}a\\b\\c\end{pmatrix}\in\mathbb{R}^3|Ax=B, x\in \...
0
votes
2answers
28 views

How do I interpret the results of Gaussian elimination of two linear systems that have the same coefficient matrix?

The systems of linear equations $$x_1 - x_2 + 2x_3 - x_4= 6$$ $$x_1 - x_3 + x_4 = 4$$ $$2x_1 + x_2 + 3x_3 - 4x_4 = -2$$ $$-x_2 + x_3 - x_4 = 5$$ and $$x_1 - x_2 + 2x_3 - x_4= 1$$ $$x_1 - x_3 + x_4 = ...
1
vote
0answers
36 views

Homology over $\mathbb{Q}$ using Gaussian elimination for differential matrix boundary operators

The Smith normal form of an integer matrix $A\in\text{Mat}_{m \times n}(\mathbb{Z})$ is a factorization $A=UDV$ for: $D\in\text{Mat}_{m\times n}(\mathbb{Z})$ Each diagonal entry of $D$ divides the ...
0
votes
1answer
230 views

Gaussian elimination with 4 variables

After this step however, I end up with 2 simultanious equations but still with four unknowns, I'm not sure if my gaussian elimination is wrong or not but how will i find the exact values of x,y,z and ...
0
votes
1answer
26 views

Find values of a and b for different dim(V).

Given the solution space V, $$ \left\{ \begin{array}{c} x_1+2x_2-x_3-5x_4=0 \\ -x_1+3x_3+5x_4=0 \\ x_1+x_2+ax_3+bx_4=0 \end{array} \right. $$ By applying Gaussian Jordan Elimination, I get from $...
3
votes
1answer
104 views

For what values of k does this system of equations have a unique / infinite / no solutions?

My system of equations is: \begin{cases} x + 5y- 6z = 2 \\ kx + y - z = 3 \\ 5x - ky + 3z = 7 \end{cases} So the augmented matrix is: $$ \left[ \begin{array}{ccc|c} 1&5&-6&2\\ k&...
0
votes
0answers
70 views

Matrix Operations and Dependent Variables

Consider the following systems along with the corresponding substitutions: \begin{align} \text{System 1} \\ 2x^2 + 3y + 5z^z & = 7 \\ 4x^2 + 9y + 10z^z & = 2 \\ x^2 + y = 2z^z & = 1 \end{...
4
votes
1answer
113 views

How to find the steady state probability of a markov chain using gaussian elimination?

Need help understanding how to properly setup the gaussian table. How/when do I use the last row ($\pi_1+\pi_2+\pi_3+\pi_4 =1$) of the systems? Does it appear as $\left[1\;1\;1\;1\;|\;1 \right] $from ...
1
vote
1answer
42 views

How to find this inverse matrix using Gauss-Jordan?

I am trying to find the inverse matrix of $$\begin{pmatrix} \ln\left(x\right) & -1\\ \:\:1 & \ln\left(x\right) \end{pmatrix}$$ using the Gauss-Jordan method. Using a different method I could ...