Questions on the various algorithms used in linear algebra computations (matrix computations).

learn more… | top users | synonyms

1
vote
1answer
44 views

Data structure for a symmetric $n\times n$ matrix

Suppose you are given a symmetric matrix $A\in\mathbb{R}^{n\times n}$ and consider the computation of the matrix vector product $A u \rightarrow v$ where $u\in\mathbb{R}^n$ is given and $v\in\mathbb{R}...
0
votes
0answers
69 views

What is the fastest known algorithm for finding eigenvalues?

What is the fastest known algorithm for finding eigenvalues? Second and third fast are also of interest if they are simpler, basically anything better than the standard solve characteristic polynomial ...
5
votes
2answers
76 views

Numerical Calculation of Eigenvalues of a large real Symmetric tridiagonal matrix

If I have an $N \times N$ matrix where every entry is zero except for along the super-diagonal and sub-diagonal, where the each entry is the conjugate of the last, like the following $5 \times 5$ ...
0
votes
0answers
33 views

Question on SVD Uniqueness Proof

I have problem understanding the proof of uniqueness for SVD by by Trefethen & Bau. If the lengths of the semi-axes of the hyper-ellipse are distinct, then semi-axes themselves are ...
0
votes
1answer
38 views

Household reflector or transformation

Let $A\in\mathbb{R}^{n\times k}$, $n\geq k$, and $rank(A) = k$. Consider the use of Household reflectors, $H_i$, $1\leq i\leq k$, to transform $A$ to upper trapezoidal form, i.e., $$H_{k}H_{k-1}\ldots ...
2
votes
3answers
75 views

What is the significance of reversing the polarity of the negative eigenvalues of a symmetric matrix?

Consider a full rank $n\times n$ symmetric matrix $A$ (coming from a set of physical measurements). I do an eigendecomposition of this matrix as $$A = E V E^T$$ Most of the eigenvalues are positive, ...
0
votes
0answers
43 views

Linear system equations

I need to get, preferably by a numerical method, a solutions of: $$\left\{\begin{array}{lll} 2\sum_{i=1}^n b_{ik}x_i+x_{n+1}=0&\text{for}& k=1,2\ldots,n\\ \sum_{i=1}^n x_i=0 \end{array}\right.$...
0
votes
1answer
32 views

Vector norm lemma and proof

I have a question from Numerical linear algebra book by Trefethen & Bau : Let $\|\cdot\|$ denote any norm on $C^m$. The corresponding dual norm $\|\cdot\|'$ is defined by the formula $\|x\...
0
votes
1answer
24 views

[Part of a system of linear equations!]: Find $B$ such that $A = B\times C$, but $C\times C'$ is non-invertable

I have the following Equation: $A = B\times C$ $A$ is a $(N\times 1)$ Known Matrix $B$ is a $(N\times M)$ Unknown Matrix, where $N>M$ $C$ is a $(M\times 1)$ Known Matrix $C\times C'$ is a non-...
0
votes
1answer
21 views

Elementary reflector $Q$ is orthogonal iff

Recall that an elementary reflector has the form $Q = I + \alpha xx^T\in\mathbb{R}^{n\times n}$ with $\|x\|_{2}\neq 0$. Show that $Q$ is orthogonal iff $$\alpha = \frac{-2}{x^Tx} \ \ \text{or} \ \ \...
0
votes
0answers
26 views

Query about the Moore Penrose pseudoinverse method

I have recently discovered the Moore-Penrose psuedoinverse method, and I am currently testing the waters with it. I noticed if I have a system, say $$a_1x_1=0$$ $$a_2x_1+a_3x_2=0$$ $$\vdots$$ $$...
1
vote
0answers
48 views

Dual Norm proof

Let $\|.\|$ denote any norm on $C^m$. The corresponding dual norm $\|.\|'$ is defined by the formula $\|x\|' = sup_{\|y\|=1}|y^*x|$. (a)Prove that $\|.\|'$ is a norm? (b) Let $x, y \in C^m $ with ...
1
vote
1answer
67 views

If the determinant of a matrix goes to infinity, does it means it has no inverse?

Context I have a linear time-invariant (single-input, single-output) system in state space representation (https://en.wikipedia.org/wiki/State-space_representation#Linear_systems): $$ \mathbf{x'}(t) ...
0
votes
1answer
21 views

Computing $PAQ = LU$ using Gaussian elimination with complete pivoting

Suppose $PAQ = LU$ is computed via Gaussian elimination with complete pivoting. Show that there is no element in $e_i^{T}U$ i.e., row $i$ of $U$, whose magnitude is larger than $|\mu_{ii}| = |e_i^{T}U ...
0
votes
1answer
27 views

Matlab algorithm for non-orthogonal diagonalization of symmetric matrices

I need to find a basis in which the symmetric bilinear form given by the n x n symmetric matrix which has 2's along the diagonal and 1's everywhere else becomes the identity. That is, if S denotes ...
0
votes
0answers
41 views

Numerical method for solving equation with $u \frac{\mathrm{d}u}{\mathrm{d}x} + u$

I'm looking for a finite difference method to solve $$a(x) u \frac{\mathrm{d}u}{\mathrm{d}x} + u = b(x)$$ where $u(0) = c$. I tried to do a lagging convergence on the $u$ ie $$a(x) u^{(n)} \frac{\...
0
votes
0answers
20 views

Gauss Seidel - Finite Element Method

I am solving an equation using finite element method, and for that I have to use Gauss Seidel to invert a matrix. In Gauss Seidel I am using a "while" which breaks if the absolute error reaches the ...
0
votes
1answer
18 views

Gauss transforms to factor $A = LU$

Consider a symmetric matrix $A$, i.e., $A = A^{T}$. Consider the use of Gauss transforms to factor $A = LU$ where $L$ is unit lower triangular and $U$ is upper triangular. You may assume that the ...
0
votes
2answers
49 views

Condition number for each variable

Condition number of a matrix tells us how viable it is to solve $Ax=b$ $$A= \begin{bmatrix} 1.001&1\\ 1&1 \end{bmatrix} $$ Is a matrix that would be difficult to solve numerically. However ...
1
vote
1answer
38 views

Numerical Range of A and A transpose.

I was playing around with the numerical range [NR] (or field of value) of a matrix $A \in \mathbb{C}^{n\times n}$ lately. And was actually looking for a proof to show: \begin{equation} A=A^H : F(A) = ...
0
votes
1answer
26 views

Write column form elementary matrix in terms of element form elementary matrices

Recall that any unit lower triangular matrix $L\in\mathbb{R}^{n\times n}$ can be written in factored form as \begin{equation} L = M_1 M_2\ldots M_{n-1} \end{equation} where $M_i = I + l_i e_i^{T}$ ...
1
vote
1answer
36 views

Numerical solution of heat equation on periodic domain

Consider the steady heat equation $\nabla\cdot(k(x) \nabla u)=f$ in two dimensions on a periodic domain, say $[0,1]\times[0,1]$. My goal is to solve it numerically with standard central 5-points ...
1
vote
1answer
27 views

Gaussin Elimination preserves S.P.D.

Let $A \in \mathbb{R}^{n \times n} $ be symmetric positive definite with positive diagonal entries. I'm trying to show that at each step $m$ of gaussian elimination $$ a^{(m+1)}_{ij} = a^{(m)}_{i,j} ...
0
votes
0answers
16 views

Different ways to leave linearly dependent vectors of a set of vectors

Let a set $S=\left\{ {{\mathbf{v}}_{i}}:i\in \mathbb{Z}_{n}^{+} \right\}$, where $\mathbb{Z}_{n}^{+}=\left\{ 1,2,...,n \right\}$ and ${{\mathbf{v}}_{i}}\in {{\mathbb{R}}^{m}}$ for each $i\in \mathbb{Z}...
0
votes
0answers
25 views

absolute value matrix and derivation of A^1 b

I have a question who could I solve the following sentence? Given is the vector $\vec{b} \in \mathbb{R^n}$ and the function $f : GL(n,\mathbb{R}) \to \mathbb{R}^n$ with $f(A) = A^{-1}b$. Then ...
1
vote
0answers
16 views

why does matrix balancing improve the linear systems condition number of the eigenvector matrix?

Matrix balancing or diagonal scaling, where at each iteration we choose a diagonal matrix so that the row and column norms are approximately equal (Osborne, 1960, Parlett and Reinsch, 1969, many ...
0
votes
1answer
43 views

Matrix-free conjugate gradient

In the conjugate gradient method for solving $Ax = b$, to update the search direction $p$ you would need to evaluate the matrix-vector product $Ap$, i.e. making sure that each search direction are A-...
2
votes
2answers
49 views

If $A\in \mathbb{R}^n$ is symmetric and satisfies [the following] then $A$ is positive definite.

The following being: $$A(i,i) >\sum_{j\ne i} |A(i,j)| \quad \text{for} \quad i=1,2,...,n $$ How can I prove this?
1
vote
0answers
6 views

Fast square of a row-stochastic matrix

I would like to implement the square $M^2$ of a row-stochastic matrix $M$. Running time is critical. Are there any known algorithms that exploit the special nature of $M$ and are faster than the usual ...
1
vote
1answer
60 views

Please explain the last step of this newton method for system of equations

The step of working out x$^1$. I know the above is the formula but do they actually work out the inverse of the derivative matrix, is there a quicker way to do this?
2
votes
1answer
42 views

Prove that if $\|A\|<1$, then $\|(I-A)^{-1}\|\geq {1\over1+\|A\|}$.

Prove that if $\|A\|<1$, then $\|(I-A)^{-1}\|\geq {1\over1+\|A\|}$. I'm not sure how to prove this result. I see feel like a geometric series is involved though. Any solutions or hints are ...
0
votes
1answer
24 views

Prove These Properties of the Pseudoinverse

Prove these properties of the pseudo inverse: 1) $(AA^*)^{\dagger}={A^{\dagger}}^*A^{\dagger}$; 2) $A^{\dagger}=A^*(AA^*)^{\dagger}$. I'm quite sure I need to use the four properties of the pseudo ...
0
votes
5answers
91 views

Why, if a matrix $Q$ is orthogonal, then $Q^T Q = I$?

I was looking at the definition of an orthogonal matrix, which is as follows: Square matrix $Q$ is orthogonal if its columns are pairwise orthonormal, i.e., $$Q^TQ = I$$ Hence also ...
0
votes
1answer
20 views

Bounds on a quadratic form

I am currently in the middle of a proof where it would be nice to have some estimates on the size of a quadratic form. In particular, I am looking at $$x^TAx$$ where $A$ is "small" (in the analyst's ...
0
votes
1answer
26 views

Columns of a matrix linearly independent and spans

Let $\mathbf v_1, \mathbf v_2, ...,\mathbf v_n \in \Bbb R^n$ and let $P$ be the $n\times n$ matrix whose columns are $\mathbf v_1, \mathbf v_2, ...,\mathbf v_n$ I'm wondering why the followings are ...
0
votes
0answers
26 views

Compute the condition number of the matrix and show for what $\Delta x$ it is singular

Given the laplacian $N \times N$ matrix \begin{align*} A=\frac{1}{(\Delta x)^2}\begin{pmatrix} 2&-1& & &\\ -1&2&-1& &\\ &\ddots&\ddots&\ddots&\\ &...
0
votes
1answer
24 views

Nearest singular matrix

Let the SVD of $A \in \mathbb R^{{n}*{n}} $ be given as $A=\sum_{i=0}^n \sigma_{i}u_{i}v_{i}^{T}$ where $\sigma_{1}\gt \sigma_{2}>{...}>\sigma_{n-1}=\sigma_{n}>0 $ Compute a matrix $B$ such ...
3
votes
2answers
83 views

Efficiently solving many sets of linear equations without inversion or factorization

Suppose I have the normal set of linear equations $Ax = b$. If I can store and manipulate $A$ I have a variety of techniques available to me such as inversion, factorization, or an iterative method. ...
2
votes
2answers
35 views

Reciprocal of a quadratic form

I am working with an expression of the form $$ \frac{x^TAx}{{x^TBx}}$$ and would like to simplify it. I understand that vectors do not have inverses, but viewing the bottom number as a 1 by 1 matrix, $...
0
votes
1answer
16 views

Reference that Explains Preconditioning

I would like to understand Preconditioning techniques and why they work. Could someone provide a good reference for this type of information?
0
votes
1answer
28 views

How to find matrix $A$ from the relation: $A\times (A^TA)^{-1}\times A^T = B$

Kindly help me in the following: I have two Matrices, $A$ of size $(n\times m)$; and $B$ of size $(n\times n)$, where $n>m$. $A$ is unknown, but $B$ is known. $(A^TA)$ is invertible $B$ is ...
0
votes
3answers
40 views

Real problems solved with systems

Can anybody tell me where can I find some REAL problems (i.e. form real life) that can be solved using a 3x3 system of linear equations? Or, can anybody give me an example? A solution could be a ...
0
votes
2answers
33 views

solving an XOR matrix

I'm working on a somewhat-unique linear algebra problem arising from XORing files together in order to encode them, and then figuring out how to subsequently recreate the original files from the ...
2
votes
2answers
45 views

Show that the matrix $AA^T+\alpha I$ is positive definite, where $\alpha >0$ and $A$ is an $m\times n$ real matrix.

Show that the matrix $AA^T+\alpha I$ is positive definite, where $\alpha >0$ and $A$ is an $m\times n$ real matrix. So I need to show that $x^T(AA^T+\alpha I)x>0$ for all vectors $x$. I'm ...
1
vote
0answers
28 views

Numerical stability of computational results

Let z be a function of a finite number of variables i.e. z=f(a,b,c,...). If we have the mathematical formula connecting z and the variables, we can determine how the value of z varies with a change ...
1
vote
1answer
20 views

Normal system of the least square method

I'm trying to show the following. $Pa$ is the approximation system of $y$. I want to show that finding the minimmum for the function $$f(a,y)=||Pa-y||_2^2$$ is equivalent to solve the normal system of ...
0
votes
0answers
13 views

Determinants using Row Reduction replacement

I am aware replacement does not affect the value of determinant when doing a row reduction. However, I realised there isn't a good explanation on how to handle different forms of replacement when ...
0
votes
1answer
17 views

Number of iterations for Gauss-Seidel

I am having some difficulty understanding the following solved problem: Question: Shouldn't we have $||T||^k_{\infty} ||e^{0}||_{\infty} \leq 10^{-6}$ instead? Where does the $5$ come from? And ...
3
votes
1answer
59 views

Detecting singular system during Cholesky resolution

I am solving small linear systems with a symmetric positive matrix by the method of Cholesky, without pivoting. "Bad" matrices are detected when you take the square root of a diagonal element, which ...
1
vote
2answers
20 views

Turning certain elements of a Matrix to zero through multiplication

Good evening, I apologize for the somewhat dumb question, I have to confess, Linear Algebra is not my strong suit. Secondly, the aim of this question is to apply this process to Excel - using VBA. ...