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

learn more… | top users | synonyms

0
votes
1answer
19 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 ...
2
votes
2answers
22 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
0answers
6 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
26 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
38 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
22 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
41 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
19 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
18 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
9 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 ...
-5
votes
0answers
19 views

SYMMETRIC OVER RELAXATION IN C [closed]

Can anybody give me a c-program for successive over relaxation?
0
votes
1answer
15 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 ...
-1
votes
0answers
7 views

Numerical Solution of Matrix with Diagonal Elements of Highly Varying Order

I am trying to solve following set of equations: A(i,i-2)*u(i-2) + A(i,i-1)*u(i-1) + (A(i,i)+β(i) )*u(i) + A(i,i+1)*u(i+1) + A(i,i+2)*u(i+2)= B(i) + β(i) where i=1:1000000 If values of β ...
2
votes
1answer
45 views
+100

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
19 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. ...
0
votes
0answers
20 views

Given a triangular matrix $T$, can we find an upper bound for $\| |T^{-1}||T|\|$?

Given a triangular matrix $T$, can we find an upper bound for $\| |T^{-1}||T|\|$, where $|T| =|[T_{ij}]| = [|T_{ij}|]$ ?
0
votes
0answers
8 views

Condition number of preconditioned system

Suppose we are solving an ill-conditioned system $Ax = b$, and we are trying to solve it using preconditioned technique. Given $\kappa (T)\approx \kappa(A)$, where $\kappa(A)$ is condition number of ...
1
vote
0answers
39 views

Why is it difficult (and not precise) to compute the rank of large matrix numerically?

I have a general question. I have a large square matrix ($n> 1000$) and it is needed to compute the rank of this matrix. I am reading that the computation of the rank for large matrices, can make ...
1
vote
1answer
33 views

Is an orthogonal matrix necessarily a permutation matrix?

Is an orthogonal matrix necessarily a permutation matrix? I believe the answer is no as a permutation matrix is a special case of an orthogonal matrix, but I am having a trouble finding a ...
0
votes
1answer
15 views

Proof with an Artificial Power Method

Suppose $A$ is $m\times m$ and has a complete set of orthonormal eigenvectors, $q_1, \ldots , q_m$, and with corresponding eigenvalues $\lambda_1,\ldots , \lambda_m$. Assume that the ordering is such ...
1
vote
2answers
13 views

Robustly map rotation matrix to axis-angle

The Wikipedia article for rotation matrix gives the following formula for converting from rotation matrix, $Q$, to axis-angle, $u$ and $\theta$: $$ \begin{align} x &= Q_{zy} - Q_{yz} \\ y &= ...
0
votes
0answers
10 views

Error estimate in iterative refinement for solving a linear system

The iterative refinement can be illustrated as follows: given an approximate solution $\hat{x}$ of the system $Ax = b$, at the $n^{th}$ step of the refinement, $r = b- A\hat{x}^{(n)}$, Solve ...
0
votes
0answers
25 views

In practice what is (modified) Gram Schmidt used for?

Modified Gram-Schmidt is known to be numerically less stable than methods like Householder orthogonalization and also not quite as fast at approximately $2mn^2$ flops. So in practice do we ever use ...
0
votes
1answer
23 views

on a characterization of convergent matrices

Let $A\in \mathbb R^{n\times n}$ a matrix. It's known that the following statements are equivalent: 1) $A$ is convergent, namely $\lim_{k\to\infty}(A^k)_{ij}=0$ 2) $\lim_{k\to\infty}||A^k||=0$ for ...
1
vote
1answer
24 views

eigenvalues lesser than 1 implies affine maps are eventually contractive

Consider $(\mathbb R^n,d)$ where $d$ is the Euclidean metric. A map $w:\mathbb R^n\to \mathbb R^n$ is said $\textbf{contractive}$ if there exists $0<s<1$ such that for every $x,y\in \mathbb R^n$ ...
1
vote
1answer
26 views

Determining the most appropriate set of eigenmodes for a modal decomposition of an experimental data set

I have a complex vector of the transverse amplitude and phase distribution of a laser beam, derived from experimental data. When modelling these field distributions, ordinarily the eigenmodes of the ...
1
vote
0answers
24 views

Eigenvalue equation and the diffusion equation

I am running some finite-element software on Matlab that generates solutions to the diffusion equation over a punctured, rectangular domain. This is the same as the $k \times k$ matrix system ...
0
votes
0answers
26 views

Finding eigenvectors of the Laplacian operator

I am running some finite-element software on Matlab that generates solutions to the diffusion equation over a punctured, rectangular domain. This is the same as the $k \times k$ matrix system ...
0
votes
1answer
15 views

Diagonalizing a Block Matrix with one non-zero Block column

I am trying to diagonalize $(M+N) \times (M+N)$ matrix $G\Gamma_LG^\dagger\Gamma_R $$ = \left(\begin{array}{cc} 0_{M\times M} & A_{M\times N} \\ 0_{N\times M} & B_{N\times N} ...
4
votes
1answer
46 views

eigenvalues lesser than $1$ implies contractive map

Consider $(\mathbb R^n,d)$ where $d$ is the Euclidean metric. A map $w:\mathbb R^n\to \mathbb R^n$ is said contractive if there exists $0<s<1$ such that for every $x,y\in \mathbb R^n$ we have ...
0
votes
0answers
35 views

What are useful mappings (operators) in image reconstruction

I'd like to ask the technician mates to provide some information regarding mappings and image reconstruction operators. Please, if possible, provide some articles and helpful discussions about useful ...
1
vote
1answer
60 views

why do we say SVD can handle singular matrx when doing least square? Comparison of SVD and QR decomposition

I don't quite understand why we say that QR decomposition doesn't handle singular matrix, while SVD does when they are used for least square problem? My example in Matlab seems to support the ...
0
votes
0answers
11 views

SVD of Cholesky Factor

I am working through the book Fundamentals of Matrix Computations by David Watkins, and I ran into this one and it's stumping me. In my head, I understand the basic premise of it. However, I can't ...
0
votes
0answers
12 views

SVD Transpose Equations

$$Av_i= \begin{cases} \sigma_iu_i & i = 1, \ldots , r \\ 0 & i = r+1, \ldots , m \end{cases}$$ $$A^Tu_i= \begin{cases} \sigma_iv_i & i = 1, \ldots , r \\ 0 & i = r+1, \ldots , m ...
1
vote
0answers
23 views

Spectral relaxation of k-means clustering

I am working on a presentation on Spectral relaxation of k-means clustering (http://papers.nips.cc/paper/1992-spectral-relaxation-for-k-means-clustering.pdf) and I am a bit stuck. I understand ...
2
votes
0answers
19 views

Is it possible to design a strongly stable linear multistep method of order 7 which has stiff decay

I'm studying for a test and I'd like to know is it possible to design a strongly stable linear multistep method of order 7 which has stiff decay. I have no clue to verify the claim. Can anyone give me ...
1
vote
0answers
16 views

Is it possible to construct a consistent unstable one step method of order 2? why?

Is it possible to construct a consistent unstable one step method of order 2? why? I think the answer is no but I have no clue to prove it. Can anyone give me some explanations? Thank you in ...
1
vote
1answer
38 views

Proving Equality of the Induced Matrix Norm

I need to prove that the induced matrix norm satisfies $$\|A\| = \max_{\|x\| = 1} \|Ax\|$$ Here's what I've done so far, and I'm not sure how to make the connection. By definition, $$\|A\| = ...
0
votes
0answers
17 views

question about dimensions.

$A\in\mathbb{R}^{n\times n}$, when solving $Ax=b$ numerically in projection method, we approximate the exact solution $x^*$ by $y$ in the subspace $K$ which has the dimension $m$. my textbook said ...
1
vote
1answer
36 views

Proving that $I-EA^{-1} = I+EA^{-1} + o(RelError(\tilde{A},A))$

Let $A\in\mathbb{R}^{n\times n}$ be a non-singular matrix and let $\tilde{A} = A-E$ be an approximation of $A$. The relative error of this approximation is $$RelError(\tilde{A},A) = \frac{\| ...
2
votes
1answer
20 views

Block Matrix Nonsingular $\iff v^T A^{-1} u\neq 0$

Here is the given question and my work so far: Question: Let $A$ be an $n \times n$ invertible matrix, and let $u$ and $v$ be two vectors in $\mathbb{R}^n$. Find the necessary and sufficient ...
1
vote
1answer
36 views

MATLAB “back slash” computation [closed]

I am looking at a MATLAB code that times the backslash operator for several cases. I will list the cases below: Note: all of these are for m = 5000 1) Z = randn(m,m); A = Z'*Z; b = randn(m,1); tic; ...
2
votes
0answers
30 views

LU Decomposition vs. QR Decomposition for similar problems

Suppose I want to solve the 2D Poisson equation with Neumann boundary conditions. The solution is non-unique up to an additive constant. I have previously asked a related question here for the 1D ...
0
votes
0answers
20 views

Applications of Khatri-Rao matrices

I'm interested in what applications there are for Khatri-Rao matrices, and in particular for solving linear systems of equations involving Khatri-Rao matrices. A Khatri-Rao matrix is a block matrix ...
1
vote
0answers
19 views

Is there a way to find if there exists a solution such that all the variables in a system of linear equations are either 0 or 1 in P time?

Note this is different from Binary Integer Programming as it does not involve inequalities. An example would be a+b = 1. A solution would be a = 0, b = 1. I just want 1 solution, or even if there ...
0
votes
0answers
16 views

Why does biconjugate gradient (BiCG) work for nonsymmetric matrices?

After looking through the derivation of CG, I understand why it requires the coefficient matrix $A$ to be symmetric, since the property is used to produce a short recurrence relation for the ...
0
votes
1answer
25 views

Householder reflector which reflects a given vector through given subspace

I want to construct Householder reflector which reflects any vector $x \in \mathbb {R}^{n}$ through $r$ dimensional subspace $W$ of $\mathbb {R}^{n}$. Also, I want to calculate computational ...
1
vote
0answers
28 views

Numerical issues with matrix exponential for diagonalizable matrix

I am learning about computation of matrix exponentials, and have come across the technique: $$ e^A = U \operatorname{diag}(e^{\lambda_1}, e^{\lambda_2}, \ldots, e^{\lambda_n}) U^{-1}$$ Where the ...
2
votes
0answers
57 views

Eigenvalues of a sum of matrices given eigenvalues of different sum

Firstly, what I want are the eigenvalues of a sum of matrices $(A + C)$. I am not asking how to express them in terms of the eigenvalues of the summands*. What I am hoping for is that there may be ...
1
vote
0answers
15 views

$Q$ is perfectly conditioned with respect to the 2-condition number.

Show that if $Q$ is orthogonal, then: $||Q||_2 = 1$, $||Q^{-1}||_2=1$, and $\kappa_2(Q)=1$. Tell me if I'm wrong but, I'm at if $||QQ^T||_2 = ||I||_2$ then $||QQ^T||_2 = 1$ which implies that ...