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

learn more… | top users | synonyms

0
votes
1answer
24 views

Find orthogonal operator to satisfy the transformation

everyone, here I have a question as shown in the figure. firstly ,I assume the standard matrix for the operator to be $A=[a_1, a_2, a_3]$ ,and I know the property that transpose of A=inverse of A ...
0
votes
0answers
22 views

Linear System with non zeros count constraint

I trying to solve a simple linear system: $Ax=b$ But with constraints like: $\sum{x_i}=S$, Usually S = 1. $L \le x \le U$, Lower & Upper bounds (usually $0 \le x \le 1$) And "Maximum count of ...
0
votes
1answer
24 views

Simplify the following in index notation

Simplify the following in index notation $I_{s,t}\delta_{s,n}\delta_{n,t}$ Since both $\delta$ 's contain an $n$ index does it simplify to $I_{s,t}\delta_{s,t}$ Then can you simplify further since ...
2
votes
2answers
48 views

Convergence for Conjuguate gradient method

I am trying to probe this corollary in a numerical PDE book: If $A\in \mathbb{R^{n\times n}}$ is symmetric and positive definite, then the conjugate gradient method reaches the exact solution in at ...
0
votes
1answer
40 views

An Optimal Value of a Diagonal Matrix $\Xi$ in $ H = U \Xi$

We have access to very accurate estimates of matrices $H$ and $U$ (both are $n \times k$, $n > k$) such that the following relationship holds $$ H = U \Xi$$ where $\Xi$ is a $k \times k$ diagonal ...
2
votes
1answer
52 views

Why are ill-conditioned systems of equations hard to solve iteratively?

Is there some intuition as to why ill conditioned system of equations hard to solve iteratively ( i.e. the convergence is slow) ? I've read convergence proofs of several methods, but still don't have ...
0
votes
1answer
41 views

Inversing badly-conditioned square matrix: methodology

I have a badly-conditioned square matrix. I need to inverse it. For inversing, currently I'm doing the following steps: I take the badly-conditioned matrix with size of $n$ by $n$ By reduced row ...
1
vote
1answer
40 views

Recover the inverse after interative solution of a linear system

I have solved the linear system $\mathbf{A} \mathbf{x} = \mathbf{b}$ with an iterative solver. The problem is well-posed ($\mathbf{A}$ is invertible, $\mathbf{b} \ne \mathbf{0}$, blah blah blah). ...
0
votes
1answer
34 views

integration and convolution

Please can some one help me on the following integration. $$ G(\nu)=\frac{1}{\Delta t}\int_{t_a - \frac{\Delta t}{2}}^{t_a + \frac{\Delta t}{2}} f(t_a -t)e^{-2\pi\nu it}dt $$ where ...
3
votes
2answers
60 views

The purpose of LU Decomposition

I was curious if anyone could help me understand why an LU decomposition is useful from a theoretical or computational standpoint. It seems to me that it is just a way to teach students the basics of ...
0
votes
1answer
30 views

Eigen value system? solution

I have the following system. $AW = \lambda B W$ Where $A,B,W$ are matrices and $\lambda$ is a scalar. The values of $A,B$ and $\lambda$ are known. $B$ is invertible. This is a solution to an ...
0
votes
0answers
15 views

Does the Conjugate Gradient Method provide an eigenvalue estimate?

Suppose that we apply a Krylov subspace method to the linear system $A x = b$. For example, if $A$ is symmetric positive-definite, then the Conjugate Gradient method may be used. I remember that the ...
1
vote
1answer
31 views

Is LU decomposition of matrices efficient for today's standards?

This is in the spirit of a previous question of mine about the efficiency of the QR algorithm. The reason for asking is that I want to motivate some students, and I'm also curious. I do understand ...
0
votes
1answer
65 views

Norm of Outer Product

Let $x \in \mathbb{R}^N$ and $ y\in \mathbb{R}^M$. Show that $\|xy^T\|_{\infty}=\|x\|_{\infty}\>\|y\|_1$ I've been able to show the following: $\|xy^T\|_{\infty}= \|xIy^T\|_{\infty} \le ...
1
vote
0answers
25 views

LU-factorisation of a square matrix

I need to show that the following matrix cannot be factor into the product LU. \begin{equation} A=\begin{bmatrix}1&2&-1\\2&4&0\\ 0&1&-1\end{bmatrix} \end{equation} I did the ...
0
votes
0answers
30 views

Search Direction in Conjugate Gradient

Could you help me with a Conjugate Gradient question? In using CG to solve $Ax = b$, why is the search direction $p_{k+1}$ in CG chosen as a linear combination of the residual $r_k$ and previous ...
2
votes
0answers
32 views

Solving a structured partitioned linear system

I am trying to solve the following partitioned linear system, where each letter represents a block $\begin{pmatrix}-H & A^T & I_n \\ A & 0_1 & 0_2 \\ z_D & 0_2^T & ...
0
votes
1answer
41 views

Heat equation in 1D with collocation method

I want to use the collocation method to solve $u_t=u_{xx}$. I impose the PDE pointwise and expand the solution in Fourier Series: $$ \partial_{t}\sum_{k=-K}^{K}\hat{u}_{k}(t)\ ...
0
votes
1answer
14 views

Linear independence of three simple functions (2.9-22)

Why is the following set of three functions linearly independent on an interval $I$ with $x>0$ if $k_2$ can take on any value besides zero and still hold true for a zero sum or that $k_1=k_3$ which ...
1
vote
1answer
37 views

A problem about lub and glb of matrix

For any matrix $A\in \mathbb{C}^{n\times n}$, define $$lub_K(A):= \inf\{\alpha\geq 0: AK\subset \alpha K\},$$ and $$glb_K(A):= \sup\{\alpha\geq 0: \alpha K\subset AK\},$$ where $K$ is a equilibrated ...
0
votes
1answer
125 views

subtraction between sum of all elements of two symmetric matrices

Let assume that I have an $n\times n$ symmetric matrix $A$ and I know $A^{-1}$. Now, I have a new matrix $$M = \begin{pmatrix} A & b \\ b^T & c \end{pmatrix},$$ where $b$ is a vector and ...
1
vote
1answer
28 views

How to prove or disprove the matrices formula

Could some one give me some hints about the following prove of disprove: (a) If $PXX^TP^T=QXX^TQ^T$, then $PX=QX$; (b) If $PXX^T=QXX^T$, then $PX=QX$. In the above formulas, $P$, $Q$ and $X$ are ...
2
votes
1answer
49 views

Eigenvectors of transition matrices in PageRank algorithm

In my probability course, we were discussing applications of Markov Chains to computer science -- in particular, how the PageRank algorithm goes about finding stationary distributions, and thus, ranks ...
0
votes
2answers
117 views

How to solve $Ax=b$ via backward and forward substitution on Matlab

How can I solve $Ax=b$ in Matlab code via LU factorization. I know that the command [L,U]=LU(A) stores the ...
2
votes
0answers
35 views

Wiedemann for solving sparse linear equation

I am new member. I am researching in Wiedemann algorithm to find solution $x$ of $$Ax=b$$ Firstly, I will show a Wiedemann's deterministic algorithm (Algorithm 2 in paper Compute $A^ib$ for ...
0
votes
1answer
36 views

help to find SOR optimal parameter $w$

Please let following linear system as $Ax=b$: $$\begin{array}{l} 6a{x_1} + {x_2} + {x_3} = 1\\ {x_1} - 3a{x_2} + 4{x_3} = 2\\ {x_1} + {x_2} - 2a{x_3} = 3 \end{array}$$ Help me to prove that the ...
0
votes
0answers
55 views

Induced matrix p-norm

Let $\|\cdot\|_p$ denote the $p$ norm $(p≥1)$ defined for every vector $x=(x_1,x_2,\ldots,x_n)^t\in\mathbb C^n$ by $\|x\|_p=(\sum|x_j|^p)^{1/p}$ and let $|||\cdot|||_p$ denote the matrix norm defined ...
1
vote
0answers
37 views

What's the point of 1-norm matrix estimation? Why not brute force?

Calculating (brute-force) 1-norm of a square matrix should take $O(n^2)$ operations, with a small factor involved. Apparently, there is an algorithm (link) for estimating 1-norm that takes $O(n^2 t)$ ...
3
votes
2answers
59 views

Calculating the determinant of $A$ with $A_{ij}=a$ for $i<j$, $A_{ij}=-a$ for $i>j$, $A_{ii}=x$, using a pen and paper

Let $$A = \left[\begin{array}{cccccc} x&a&a&a&\dotsm&a\\ -a&x&a&a&\dotsm&a\\ -a&-a&x&a&\dotsm&a\\ -a&-a&-a&x&\dotsm&a\\ ...
0
votes
1answer
29 views

Finding the minimum of Condition number for this matrix

Suppose $A=\left[ {\begin{array}{*{20}{c}} {0.1\alpha }&{0.1\alpha }\\ 1&{1.5} \end{array}} \right]$. How can we find minimum of condition number $k(A)=\Vert A\Vert \Vert A^{-1} \Vert$ (Assume ...
1
vote
0answers
32 views

Is it better to compute $A^tA$ once and then $Ax$ several times or compute $y=Ax$ and then $A^ty$ every time?

So I have this algorithm which given a matrix $A$ it assigns $A=A^tA$ outside the loop and then on the algorithm loop it solves multiple instances of $Ax$ for different $x$s, (meaning that it's ...
3
votes
2answers
86 views

Good Textbook in Numerical PDEs?

I am currently taking a course on Numerical PDE. The course covers the following topics listed below. Chapter 1: Solutions to Partial Dierential Equations: Chapter 2: Introduction to Finite ...
2
votes
1answer
43 views

Restoring matrix from covariance matrix

Given $ A^TA $, how to restore $A$? (Any $A$ which produces this $ A^TA $). Given matrix $ A^TA $, vector $b$, and vector $Ab$, how to restore a matrix $A$ ? Correction to 2: The vector $A^Tb$, ...
0
votes
1answer
53 views

Why won't my conjugate gradient algorithm work?

I made this simple Conjugate Algorithm on Matlab n = length(b); r0 = b - A*x0; p0=r0; k=1; n0=(r0')*r0; while n0 >= eps && k <= n ...
0
votes
0answers
81 views

update cholesky factorization

I need to compute cholesky(H'*H) where H is a big sparse rectangular matrix. After that H is modified by adding several lines. That is Hn = [H ; line_1 ; ... ; line_n] in Matlab. How can I recompute ...
1
vote
0answers
42 views

matrix with positive diagonal elements

I was wondering if a symmetric matrix with positive elements only in the diagonal (negative elsewhere) is any special beside the symmetry. Thanks in advance
2
votes
0answers
41 views

Find the solution of linear equation using Wiedemann/ Krylov method

I am using Wiedemann (some literature called Krylov method) to find the solution of a linear equation that defined as $$Mx=b$$ Instead of resolving entire elements of x (size $K \times 1$), we can ...
1
vote
1answer
19 views

If normal linear regression finds $A$ such that $AX \sim Y$, then how do I solve $BAX \sim Y$?

If normal linear regression finds $A$ such that $$AX \sim Y$$ then how should I solve $$BAX \sim Y$$ where $B$, $X$ and $Y$ are given (non-invertible) matrices? I could of course derive the solution ...
0
votes
0answers
19 views

order of convergence for approximations

Let $u \in L^{2}(0,1)$ and $0 < x_{1}< x_{2}<... < x_{n} = 1$, where x$_{k}$ = k$\cdot$h, n$\cdot$h = 1, a partition of the interval [0,1]. Define I$_{k}$(x) = 1 if x $\in$ [x$_{k}$, ...
0
votes
0answers
19 views

Location and perturbation of eigenvalues

This is a problem from Horn and Johnson's Matrix Analysis. I'm having trouble showing the bolded parts in the following paragraphs. In fact, I don't really understand what the sentences mean. I would ...
0
votes
1answer
39 views

Eigenvalue inequalities for Hermitian matrices

This is a problem from Horn and Johnson's Matrix Analysis. I've tried to follow the problem but I can't find a way to lead to the conclusion the problem is suggesting. Any solutions, hints, or ...
0
votes
0answers
28 views

A problem on Gersgorin cirle passing through the eigenvalue of an absolute matrix

I'm having trouble solving the following problem. I think I need to show that the matrix $D^{-1}|A|D$ has property SC, but I can't come up with a way to show it. I would really appreciate any ...
0
votes
1answer
18 views

A problem about a theorem on irreducible matrix

I'm stuck on a problem where I need to find a counterexample. I'm not sure how to come up with a reducible matrix to show that it doesn't satisfy the result of the following corollary. Any solutions, ...
0
votes
1answer
21 views

Suppose that $A \in M_n$ is strictly diagonally dominant. Show that $|a_{kk}|$ $\lt C_k'$, for at least one value of $k$

Suppose that $A \in M_n$ is strictly diagonally dominant. Show that $|a_{kk}|$$\gt C_k'$, for at least one value of $k=1,\dots, n$, where $C_k'$ denotes $A$'s deleted absolute column sums ($a_{kk}$ is ...
2
votes
1answer
38 views

Suppose that the $n$ Gersgorin discs of $A \in M_n$ are mutually disjoint. If $A$ is real, show that every eigenvalue of $A$ is real.

Suppose that the $n$ Gersgorin discs of $A \in M_n$ are mutually disjoint. (a) If $A$ is real, show that every eigenvalue of $A$ is real. (b) If $A \in M_n$ has real main diagonal entries and its ...
2
votes
1answer
31 views

Show that the intersection taken over the Gersgorin discs of all similar matrices of $A$ $=$ $\sigma (A)$

Show that $\bigcap_S G(S^{-1}AS)$ $=$ $\sigma (A)$; the intersection is taken over all nonsingular $S$, and $\sigma (A)$ is the spectrum of $A$. I'm lost as how to even begin to prove this fact. Any ...
1
vote
2answers
33 views

Domain for which this matrix is positive definite

What is the domain for which this matrix is positive definite? $$\left(\begin{array}{cc} 12x^2 & 1 \\ 1 & 2 \\ \end{array}\right)$$ I'm trying to figure this out. I know the ...
1
vote
0answers
58 views

Rayleigh quotient ($|r(q)-\lambda|=O(||q-x||_2^2)$ ?)

how to show $|r(q)-\lambda|=O(||q-x||_2^2)$ $r(q)=q^*Aq/(q^*q)$ and $\lambda$ is an eigenvalue, A is a Hermitian matrix. x is the unit eigenvector corresponding to $\lambda$. and q is a unit vector. ...
0
votes
1answer
74 views

Interpolation of polynomials

let $f(x)=2^x$ and $x_0=1$, $x_1=2$, $x_2=3$. Use divided differences to compute the interpolation polynomial $P(x)$ satisfying $P(x_i)=f(x_i)$, i=0,1,2 and $P'(x_1)=f'(x_1)$ and estimate error ...
0
votes
0answers
35 views

Is the following matrix Upper Hessenberg?

Does $$ A = \begin{pmatrix} 1 & 1 \\ -1 & -1 \end{pmatrix}$$ properly satisfy the definition of upper Hessenberg?